布尔函数电路复杂度相关证明问题问询：特定函数存在性与电路规模类严格包含关系

嘿，这个问题问得很到位，刚好可以用香农的计数论证（就是你提到的Shannon’s counting argument）来解决，我给你一步步理清楚思路：

首先先解决第一个核心问题：怎么证明存在满足那两个条件的布尔函数。

第一步：明确目标函数的范围 #

首先，对于每个n，我们只考虑仅依赖输入前$k(n)=\lceil 2.1 \log n \rceil$位的布尔函数。先算一下这类函数的总数：$k(n)$位输入总共有$2^{{k(n)}$种可能的取值，每个取值对应0或1的输出，所以总共有$2}{2^{{k(n)}}$个不同的函数。把$k(n)$代入的话，$2}{k(n)} \geq n^{2.1}$（因为$k(n) \geq 2.1 \log n$，两边取2的幂就是$2^{k(n)} \geq 2^{\log n^{2.1}}=n{2.1}$），所以这类函数的总数至少是$2^{n{2.1}}$。

第二步：计算$O(n^2)$规模电路能表示的函数数量 #

接下来，我们算一下，对于输入长度n，规模为$m=O(n^{2)$的布尔电路（门数是$O(n}2)$，门类型是AND/OR/NOT，扇出2），总共能表示多少种不同的布尔函数。

每个规模为m的电路可以被编码成一个有限的字符串：每个门需要指定类型（3种选择：AND/OR/NOT），还要指定输入的来源——比如AND/OR门需要选两个输入（可以是前m个门里的任意一个，或者n个输入变量里的任意一个），NOT门选一个输入。不过不用纠结太细的编码细节，香农计数的核心是：规模为m的不同电路数量是$2^{O(m \log m)}$。

这里$m=O(n^{2)$，代入的话，电路数量就是$2}{O(n^2 \log n)}$。

第三步：比较两者的增长速度 #

现在我们把两个数量放一起比：

• 目标函数的总数：$2^{n{2.1}}$
• $O(n^{2)$规模电路能表示的函数数量：$2}{O(n^2 \log n)}$

当n足够大时，$n^{{2.1}$的增长速度明显快于$n}2 \log n$（因为指数2.1>2，而$\log n$的增长远慢于多项式），所以必然存在大量的这类“仅依赖前$k(n)$位”的布尔函数，是$O(n^{2)$规模电路完全无法表示的。这就直接证明了满足条件1和2的函数存在——因为我们找到了这样的函数，它们只看输入的对数长度前缀，却无法被$O(n}2)$规模的电路族识别。

接下来解决第二个问题：能不能得出$\text{SIZE}(n^2) \subset \text{SIZE}(n^3)$的严格包含关系？ #

当然可以，而且刚好可以用我们刚才“非构造性证明存在”的那个函数来验证：

刚才我们证明了存在一个函数$f$，它**不在$\text{SIZE}(n^{2)$**里（因为无法被$O(n}2)$规模的电路族识别）。那它在不在$\text{SIZE}(n^3)$里呢？

答案是肯定的：因为$f$只依赖$k(n)=\lceil 2.1 \log n \rceil$位输入，对于这类函数，我们可以用**析取范式（DNF）或者合取范式（CNF）**来构造电路。比如DNF的话，每个满足$f(x)=1$的$k(n)$位输入对应一个AND门，然后把所有这些AND门用OR门连起来，总门数是$O(2^{k(n)})=O(n{2.1})$，而$n^{{2.1}$显然是$O(n}3)$（当$n \geq 2$时，$n^{2.1} \leq n^{3$）。所以这个函数$f$属于$\text{SIZE}(n}3)$。

既然存在一个函数在$\text{SIZE}(n^{3)$里但不在$\text{SIZE}(n}2)$里，那显然$\text{SIZE}(n^{2)$是$\text{SIZE}(n}3)$的真子集，也就是$\text{SIZE}(n^2) \subset \text{SIZE}(n^3)$成立。

补充一点：为什么计数论证在这里这么好用？ #

香农计数论证的核心思想就是“穷举法”的反向：当我们要证明存在某个无法被某类计算模型表示的对象时，只需要算出模型能表示的对象总数远小于目标对象的总数，那必然存在漏网之鱼——这也是电路复杂度里证明“存在难函数”的经典技巧，完全不需要构造具体的函数，只需要用计数来“非构造性”地证明存在性。

备注：内容来源于stack exchange，提问作者user1326505