06 电路复杂性

在图灵机的模型下，复杂性理论的研究遇到了许多困难，至今为止许多符合直观的命题都还只是猜想而无法得到证明（比如$\text{P}\neq \text{NP}$）。于是人们意识到，造成这样的研究瓶颈的原因是“图灵机”作为模型本身太过复杂。图灵机刻画了一切计算，其使用的方法是描述若干条纸带以及读写头的移动。这样的模型明显的缺陷是其计算过程和问题本身没有结构上的对应，所以我们说图灵机的计算是“非结构化”的。鉴于此，人们开始研究其它一些更具体的模型的复杂性理论，例如决策树复杂性、通讯复杂性、证明复杂性、电路复杂性等等。其中，电路复杂性是最直观反映计算的结构的模型。起初人们寄希望于通过研究电路复杂性，从而解决复杂性中的一些诸如$\text{P}\neq\text{NP}$之类的根本性问题。然而一段时间的研究后电路复杂性的理论也因为变得太过复杂而遇到瓶颈。事实上到目前为止，基于任何这些具体模型的复杂性理论都遇到了瓶颈。然而即便如此，基于电路复杂性的理论依然对研究图灵机的复杂性理论大有帮助。例如接下来我们会看到，电路复杂性能够帮助我们研究$\text{P}\neq \text{NP}$，研究并行计算，帮助我们刻画$\text{P}$类的内部结构等等。

电路模型(Circuit Model)

一个布尔电路由若干与门、或门、非门，$n$个输入的bit，1个输出的bit组成。既然我们研究判定问题就是研究二进制串的输入到一个01bit的输出的函数，所以显然我们可以用布尔电路计算判定问题。与图灵机不同的是，一台图灵机可以接受任意长度的输入，而一个布尔电路只能接受固定长度的输入。所以为了判定一个问题$f:\{0,1\}^\ast\to\{0,1\}$，我们需要一族电路$\{C_n\}_{n\in\N}$，其中$C_n$表示一个有$n$个输入的布尔电路。

按照以上方法，一族布尔电路在判定一个问题时在不同输入上可以有完全不同形态的电路构造。这使得布尔电路在计算能力上强于图灵机。我们可以考虑这样一个事实：对于任意的布尔函数$f:\{0,1\}^\ast\to\{0,1\}$，我们都可以对任何输入长度$n$列出对应的真值表，对每个真值表很容易构造一个布尔电路，所以理论上一族布尔电路可以描述任何布尔函数。这其中包括了图灵机不可计算的布尔函数。

电路复杂性(Circuit Complexity)

尽管我们理论上可以用布尔电路计算任何判定问题，也即电路的可计算理论是一个无需深入探讨的问题，但基于真值表的构造通常是指数量级的：电路的复杂性是一个需要深入探讨的问题。自然的，一个电路的复杂性应当对应于这个电路中与、或、非门的总数，我们把这个总数称为电路的大小(size)。用$|C|$表示电路$C$的大小，那么可以定义：判定问题$L$在电路复杂性为$S(n)$的类中当且仅当存在一族电路$\{C_n\}_{n\in \N}$使得$|C_n|\leq S(n)$，记为$L\in\text{SIZE}(S(n))$。注意到在定义中我们使用了“存在”，也就是我们默认选取出能够描述此问题的最小电路。尤其需要注意的是，以上定义与图灵机中的复杂性类定义不同，我们没有用大$O$记号省略常数。原因是，我们将会证明电路复杂性是对常数敏感的，比如$\text{SIZE}(S(n))$和$\text{SIZE}(3S(n))$将对应不同的复杂性类。

在电路复杂性中，很重要的一个基本认识是，“几乎所有”的布尔函数都需要一个关于输入个数$n$的指数大小的电路族来刻画。Shannon用一个计数的argument证明了，一个$n$个输入的布尔电路的大小$S$如果小于$\dfrac{2^n}{n}-o\left(\dfrac{2^n}{n}\right)$，那么它只能描述所有$n$元布尔函数的总数（$2^{2^n}$）的不超过$\dfrac{n}{2^n}$那么多比例个。也即，绝大多数的$n$元布尔函数的电路复杂性都大于$\dfrac{2^n}{n}-o\left(\dfrac{2^n}{n}\right)$。而Lupanov又证明了，最难的$n$元布尔函数的电路复杂性也不超过$\dfrac{2^n}{n}+o\left(\dfrac{2^n}{n}\right)$（其中，“最难的函数”是指计算该函数所需要的最小电路最大的那个函数）。这向我们指明，可以认为几乎所有布尔函数的电路复杂性都是指数级别的，并且绝大多数布尔函数和最难的布尔函数是一样难的。（关于最难问题的电路复杂性上下界，目前最好的结果是Frandsen-Miltersen定理：$\dfrac{2^n}{n}\left(1+\dfrac{\log n}{n}-O\left(\dfrac{1}{n}\right)\right)\leq|C_f|\leq \dfrac{2^n}{n}\left(1+3\dfrac{\log n}{n}+O\left(\dfrac{1}{n}\right)\right)$）。

值得一提的是，尽管我们证明了绝大多数问题的电路都有指数复杂性作为下界，但目前我们还找不出任何一个能证明它的下界是指数的问题。这也体现了电路复杂性理论的困难之处。

基于以上上下界的定理，可以证明电路谱系定理(Circuit Hierarchy Theorem)：若存在$\epsilon>0$满足$\dfrac{S_2(n)}{S_1(n)}>2+\epsilon$，并且$(2+\epsilon)S_1(n)>n,\dfrac{S_2(n)}{2^n/n}\to 0$，那么有$\text{SIZE}(S_1(n))\subsetneq \text{SIZE}(S_2(n))$。这就是之前提到的电路复杂性类对常数的敏感性：一个电路中门的个数每扩大两倍，就能解决一个原先大小的电路无法解决的问题。

一致电路(Uniform Circuit)

我们已经看到，电路族能够计算图灵机不可计算的问题，因此如果要用电路研究图灵机的计算复杂性理论，必须限制电路的计算能力使之和图灵机相同。关键在于，我们不能允许不同输出长度的电路有本质不同的构造方法，这种特性称为电路的“不一致性(non-uniformity)”。

我们可以引入图灵机的刻画来定义“一致电路”：称电路族$\{C_n\}_{n\in \N}$是一致的，如果存在一个图灵机对数空间可计算的函数$f$把$n$映射到$C_n$的编码。

为什么定义中用的是对数空间可计算而不是多项式时间可计算？事实上，用多项式时间可计算定义也是可以的，并且可以证明这样得到的定义和以上定义是等价的。

下面我们证明，一致电路族所能判定的问题恰好是图灵机的多项式时间复杂性类$\text{P}$中的问题。也即，一致电路族给出了$\text{P}$的一个等价刻画。这称为一致电路族定理(Uniform Circuit Family Theorem)。Proof Sketch：$\forall L$，若$L$能被一个一致电路族接受，那么说明每个输入长度的电路都可以对数空间计算得到，因此每个电路大小都是多项式的，用图灵机模拟多项式大小的电路只需要多项式的时间，因此$L\in\text{P}$；$\forall L\in \text{P}$，写出该多项式计算过程的逻辑刻画，转化为电路即可。Qed.

我们可以定义可满足性问题的电路版本$\texttt{CKT-SAT}$：$\forall x\in\{0,1\}^*,x\in\texttt{CKT-SAT}$当且仅当$x$编码了某个电路$C$且该电路存在使其输出为$1$的输入赋值。可以证明，$\texttt{CKT-SAT}$是$\text{NP}$-complete的。

带建议的图灵机(Turing Machine with Advice)

在上一节中，我们为了研究图灵机复杂性限制了电路的计算能力。在这一节中，我们考虑为了研究电路复杂性而增加图灵机的计算能力。从能够得到的结论来看，做这样的反方向研究是有帮助的。

自然，为了让图灵机获得电路的非一致性，我们需要在图灵机接受不同长度的输入时，给图灵机提供额外的信息。我们把这样的信息称为建议(advice)。我们需要为每个长度的输入提供一个建议，所以我们需要提供要给建议族(advice family) $\{\alpha_n\}_{n\in \N}$。如果存在这样一族建议，其长度满足$|\alpha_n|\leq a(n)$，并且带有建议$\alpha$的图灵机能在$T(n)$时间内判定$L$，就记$L\in \text{TIME}(T(n))/a(n)$。

我们特别关心$T(n)$为多项式，$a(n)$也为多项式的情况。这一复杂性类记为$\text{P}_{\text{/poly}}$。此时我们可以高效地把图灵机的计算能力加强到非一致电路的计算能力。非一致电路族定理(Non-Uniform Circuit Family Theorem)，指出$\text{P}_{\text{/poly}}=\bigcup\limits_{c_1,c_2}\text{SIZE}(c_1n^{c_2})$。Proof Sketch：如果$L$有非一致的多项式电路判定，那么把该电路的编码作为advice即可在图灵机上多项式模拟；如果$L$有多项式的advice能在图灵机上计算，那么利用计算的逻辑刻画可以把该计算转化为多项式电路。

我们看到，一致电路族定理和非一致电路族定理告诉我们：如果要研究多项式大小的一致电路族的复杂性类，那么只需研究$\text{P}$；如果要研究多项式大小的不一致电路族的复杂性类，那么只需研究$\text{P}_{\text{/poly}}$。

显然，$\text{P}\subseteq \text{P}_{\text{/poly}}$。所以如果想证明$\text{P}\neq \text{NP}$，只需证明$\text{NP}\subsetneq \text{P}_{\text{/poly}}$（画韦恩图）。Karp-Lipton定理指出，若$\text{NP}\subseteq \text{P}_{\text{/poly}}$，则$\text{PH}=\text{PH}_2$（多项式谱系坍缩到第二层）。这告诉我们如果无限谱系假设成立，那么即便使用非一致的电路也无法判定$\text{NP}$问题。这就是人们用电路复杂性理论研究图灵机复杂性理论的一个例子。

并行计算(Parallel Computation)

并行计算是提高计算效率的重要方法。在图灵机模型中，我们总是假设只有一个CPU在对读写图做操作，因此难以对并行计算建模。然而，电路是很容易施展并行计算的。一个电路是一个DAG，我们可以把所有输入（也就是入度为零的点）看作电路的第一层（最底层），这些点经过与、或、非门的运算后得到第一批输出，这些输出对应的节点可以看作第二层，以此类推我们可以把一个电路分层。容易注意到，每一层的所有计算在时间上都是没有相互依赖关系的，因此是可以并行的。换言之，研究一个电路在并行计算下的运行时间只需考察该电路的层数，我们称之为电路的高度(height)。

对数多项式并行类(Nick's Class)

称函数$H:\N\to\N$是电路族$\{C_n\}$的高度，当且仅当$\forall n$，$C_n$的高度不超过$H(n)$。对于判定问题$L$，如果存在一个高度函数为$O(\log^d(n))$的一致电路能够判定$L$，就记$L\in \text{NC}^d$。定义$\text{NC}=\bigcup\limits_{d\in\N}\text{NC}^d$。其中，$\text{NC}$是Nick's Class的缩写，因为这个复杂性类最早是由Nicholas Pippenger提出的。注意在定义中我们用的是一致电路，这方便与图灵机接轨。

之所以用输入长度的对数的多项式(poly-log)对高度分类，是因为我们认为polylog是作为“高效并行(efficient parallel)”的合适的定义。首先，polylog的电路大小一定是多项式大小的。并且许多重要的并行计算问题落在了polylog的某一层上：

布尔矩阵的矩阵乘法问题$(A\times A)_{ij}=\bigvee\limits_{k=1}^{n}A_{ij}\land A_{kj}$可以做这样的并行计算：首先用$n^3$个与门并行计算所有的$A_{ij}\land A_{kj}$；接着并行计算$A\times A$的每一位，由于每一位都对应第一层中特定的$n$个输出的或，所以最优的并行方式是用一个高度为$\log n$的二叉树。由此可见，布尔矩阵的乘法问题的电路高度是$\log n+1$，因此落在$\text{NC}^1$。

进一步，如果是计算布尔矩阵的幂$A^n$（注意，指数是输入长度量级的），那么用矩阵快速幂我们需要做$O(\log n)$次矩阵乘法，这些乘法是不可并行的，因此我们需要$O(\log^2 n)$高度的电路。可见$A^n$的计算落在$\text{NC}^2$。

图（有向图或无向图）可以用邻接矩阵描述。邻接矩阵是布尔矩阵。图上两点间的可达性问题($\texttt{Reachability}$)可以用邻接矩阵的幂计算得到。因此，图的可达性问题落在$\text{NC}^2$。这是一个有启发性的例子，因为一般直观上代数问题比较可并行，而图的遍历问题因为有时间先后关系看似不可并行。但通过邻接矩阵我们可以把图论问题“代数化”来使得其能够并行。

交替电路(Alternating Circuit)

在一般布尔电路中，与门、非门都只有两个输入端。因此要实现$n$个变量的或（与）需要$\log n$层。如果我们修改模型的定义，允许与门、或门有任意多个输入，那么$\log n$层就可以优化为$1$层。而把一个与或门有多个输入的电路转化为只有两个输入的电路，只需把每个多输入的门用二叉树的形式展开，因此电路的高度最多变高$\log n$倍。我们把$\text{NC}^d$类的定义修改为允许与门、或门有任意多个输入的版本，把这样的类记为$\text{AC}^d$类。根据上述讨论，有$\text{NC}^i\subseteq \text{AC}^i\subseteq \text{NC}^{i+1}$。进而，$\text{NC}=\text{AC}$。所以我们给出了一个$\text{NC}$类的等价定义。

$\text{AC}$是Alternating Circuit（交替电路）的缩写。因为当一个与门、或门可以有多个输入的时候，任何时候我们都可以把多层连续的与操作、或操作压到同一层，因此从效果上，这样的电路总是一层与、一层或交替进行的。

P-completeness

基于$\text{NC}^0\subseteq\text{NC}^1\cdots\subseteq \text{NC}^n\subseteq\cdots$的关系，我们可以把这也看作一个谱系，称为$\text{NC}$谱系。由于$\text{NC}\subseteq \text{P}$，我们可以把这个谱系看作对多项式时间类$\text{P}$的内在结构的一种刻画——$\text{P}$中问题在并行计算视角下的难易程度。为了比较难易程度自然要定义归约，显然我们此时不能用多项式归约了（那样的话所有问题都会变成完全问题），所以我们采用对数空间归约。所以如果$\text{P}$中存在某个问题$L$使得所有$\text{P}$中问题都可以归约到$L$，那么就称$L$是$\text{P}$-complete的。（可以验证，隐式对数空间可计算函数都在$\text{NC}$内，因为对数空间可计算函数的格局图的邻接矩阵是多项式大小的，因此格局图上的可达性问题是$\text{NC}$的）

可以证明，下面这个$\texttt{Circuit-Eval}$函数是$\text{P}$-complete的。这个问题包含所有有序对$(C,v)$的编码，其中$C$是布尔电路，$v$是一个$C$上的输入赋值，满足$C(v)=1$。

在$\text{NC}$谱系中，我们可以插入对数空间类$\text{L}$和非确定对数空间类$\text{NL}$。因为$\text{NC}^1$只有$\log n$层，因此总门数是$c\cdot n$，因此用确定性图灵机模拟$\text{NC}^1$的计算只需记录门的编号的计数器，这个计数器的长度是$\log(cn)=O(\log n)$，所以属于对数空间类。所以$\text{NC}^1\subseteq \text{L}$。另一方面，我们已经证明了$\text{NL}$完全问题$\texttt{Reachability}$在$\text{NC}^2$中，所以$\text{NL}\subseteq \text{NC}^2$。这样我们就得到了以下谱系：$\text{NC}^0\subseteq\text{NC}^1\subseteq \text{L}\subseteq\text{NL}\subseteq\text{NC}^2\subseteq \cdots\subseteq \text{NC}^n\subseteq\cdots\subseteq \text{P}$。遗憾的是，这一列包含关系中没有任何一个被证明是严格的。因为任何高度非常数的电路族都已经太复杂了。

对于常数高度的电路族，我们有结论$\text{AC}^0\subsetneq \text{NC}^1$。这是关于电路我们能证明的唯一一个严格包含关系。利用Hastad Switching Lemma，我们可以证明Parity Function $\oplus(x_1,\cdots,x_n)=1\iff \sharp [x_1=1]\text{ is odd}$不在$\text{AC}^0$中。