本文译自Existence of functions with exponential circuits complexity，原作者David Steurer。有删改。
本文所述定理由C. E. Shannon于1949年在The synthesis of two-terminal switching circuits提出。
我们想要表明，存在这样的位布尔函数，其需要规模的电路来计算。
核心思想是要将形如的位布尔函数的数量与小规模电路的数量进行比较（“小规模”在本文意味着规模为）。
让我们首先计算位布尔函数的个数。一般地，从一个有限集映到一个有限集的函数的个数为（你只需说服自己接受这个事实）。因此，在我们的情境中，位布尔函数的个数为。
现在，让我们计算规模电路的数量。一个规模电路是一张含有个顶点的有向无环图（DAG），每个顶点的入度至多为2。（一个顶点的入度是指指向该点的边的个数。）更进一步地，每个源顶点（入度为0）都代表一个输入变量。每个汇顶点（出度为0）都代表一个输出变量。（我们将假设只有一个汇顶点，因此也就只有一位输出。对于计数而言，这个假设并不会产生多大影响。）每个既非源顶点也非汇顶点的顶点代表一个基本布尔函数（“与、或、非”中的一个）。
我们断言，一个规模电路可以用长度至多为的二进制串完全描述。首先，我们给每个顶点一个独特的ID。因为电路只含有个顶点，因此编码一个ID只需至多的长度。那么，为了描述一个顶点，我们需要用的长度记录其ID，用的长度记录指向的顶点的ID，用的长度来记录其表示的变量或布尔函数。我们不需要记录的出度，因为该信息将被记录在指向的顶点的入度信息里。那么总的来说，我们对每个顶点花费位长来记录。因此，对整个电路的描述是不超过位的。
于是我们可以推出规模电路的个数至多为（也即长度为的二进制串的个数）。对于，这个数量远小于。它可以推出如下事实：绝大部分位布尔函数都没有规模的电路。
经过更仔细的计算可以得到，系数拓展到的时候大致就是紧的了。也就是说：每个位布尔函数都有一个规模的电路。
这些结果意味着什么呢？ 不幸的是，它们并不能提供关于这些难以计算的函数的具体形态的信息。这个下界本质上是在说一个随机的函数通常有很高的电路复杂性。我们为什么会想要计算一个特定的随机函数呢？事实上，“给出一个明确的、有趣的具有高电路复杂性（哪怕仅仅是超线性规模）的函数”目前仍是一个困难且重要的开放问题。