Computational Complexity: Circuit Complexity

Posted on Edited on In Views: Word count in article: 1.2k Reading time ≈ 4 mins.
本篇是计算复杂性（CS7313）的第五章，主要研究电路复杂性问题。

Boolean Circuit Model

布尔电路（Boolean Circuit）是一种不一致模型，对于同一个算法，不同的输入大小对应不同的布尔电路。（每个结点都有输入，也有对应的布尔运算，与、或、非）

单调电路：不包含非门的电路。

电路复杂性

电路复杂性即电路$C$包含的门的个数$|C|$。

布尔电路族：解决同一个算法的不同大小的输入的一群电路称布尔电路族（Boolean Circuit Family）$\{C _n\} _{n \in \text{N}}$，其复杂度$S(n)$定义为$\forall n, |C _n| \le S(n)$。

电路能算的图灵机不一定能算。

Nonuniform Complexity Class

电路族判定问题：如果存在一个$S(n)$大小的电路族$\{C _n\} _{n\in \text{N}}$，使得对任意$x \in \{0,1\} ^n$，$x \in L$当且仅当$C _n(x)=1$，则称该电路族判定了问题$L$，也即问题$L$是在$\textbf{SIZE}(S(n))$中的。

对非一致模型，$\textbf{SIZE}(cS(n)) \ne \textbf{SIZE}(S(n)),c > 2$。

香农定理

大多数$n$个输入的布尔函数，其电路复杂性一般大于$\frac{2 ^n}{n}-O(\frac{2 ^n}{n})$。证明的说明：

  1. $S$为电路门的个数。$3 ^S$表门有与、或、非三种，$2S$表每个门有0或1两种输入，$S+n+2$表不同的输入来源（直接输入、别的门的输出），故大小为$S$的电路个数约为$(S+n+2) ^{2S} 3 ^S$；
  2. $(S-1)!$表不同排列但功能相同的电路；
  3. $2 ^{2 ^n}$表具有$n$个输入的布尔函数的个数。

Circuit Hierachy Theorem

如果对$\epsilon > 0$，$n < (2+\epsilon)S(n) < S'(n) << 2 ^n /n$，则$\textbf{SIZE}(S(n)) \subsetneq \textbf{SIZE}(S'(n))$

Uniform Circuit

一致电路族：可在对数空间内由$1 ^n$生成$C _n$。

一致电路族能判定的问题就是$\text{P}$。

右往左：Cook-Levin归约的用条带表示的格局图可视为一个电路。

Circuit Satisfability

电路可满足问题$\textbf{CKT}-\textbf{SAT}$：一个代表输入大小为$n$的电路$C$的字符串$s$，若$\exists u \in \{0,1\} ^n$，使得$C(u)=1$，则该字符串是在$\textbf{CKT}-\textbf{SAT}$里面的。

$\textbf{CKT}-\textbf{SAT}$是$\text{NP}$完全的。

引申开来，任何NP问题都可以对数空间归约到SAT，因为CKT-SAT可以对数空间归约到SAT。

P /poly

带advice的图灵机：

  • $\text{P} _{/\text{poly}}$
  • $\text{NP} _{/\text{poly}}$
  • ...

其中advice即$\alpha _n \in \{0,1\} ^{a(n)}$。

  • 对于$L \in \text{P} _{/\text{poly}}$，$x \in L \iff \mathbb{M}(x,\alpha(n))=1$，且判定时间为多项式时间，$a(n)$亦为多项式。
  • 对于$L \in \text{NP} _{/\text{poly}}$，$x \in L \iff \mathbb{N}(x,\alpha(n))=1$，且判定时间为多项式时间，$a(n)$亦为多项式。

定理：
$$
\text{P} _{/\text{poly}}=\bigcup _c \textbf{SIZE}(cn ^c)
$$

证明：

右到左：用对$C _n$的描述作为advice，由于$C _n$是多项式的，对它的描述也是多项式的；

左到右：将格局图的计算过程翻译成电路图，并把advice烧进电路。

Karp-Lipton Theorem

显然$\textbf{P} \subseteq \textbf{P} _{/\text{poly}}$。

定理：若$\textbf{NP} \subseteq \textbf{P} _{/\text{poly}}$，则$\textbf{PH}= \Sigma _2 ^p$

只需要证明$\Pi _2 ^p\subseteq \Sigma _2 ^p$，即证明$\Pi _2 ^p-\text{SAT}\subseteq \Sigma _2 ^p-\text{SAT}$。

NC and AC

电路模型研究并行运算--同一层的门可以并行运算。

  • 有效的并行算法（Efficient Parallel Algorithm）：用多项式个处理器可以加速到对数的多项式时间的算法。

  • $\text{NC} ^d$：可被大小为$p(n)$，深度为$\log ^d (n)$的一致电路族$\{C _n\} _{n \in N}$判定的问题类。

$$
\textbf{NC} = \bigcup _{d \in \text{N}} \textbf{NC} ^d
$$

$\textbf{NC} \in \textbf{P}$

$\textbf{AC}$是$\textbf{NC}$的扩展，它可以接受无数个输入，但事实上：

$$
\textbf{AC}=\textbf{NC}
$$

可达性就是布尔矩阵连乘（$A ^n$），故$\text{Reachability} \in \textbf{NC} ^2$。

$\textbf{P}$完全

对数空间归约保持高效可并行性，即若$L \le _L L' \in \textbf{AC}$，则$L \in \textbf{AC}$。

  • 对数空间归约时，每一位的输出都可并行计算；
  • 格局图矩阵（多项式大小）的每一位都可并行计算，可在对数空间输出；
  • $\text{Reachability} \in \textbf{NC} ^2$。

$\textbf{P}$完全

$L' \in \textbf{PC}$，如果$\forall L \in \textbf{P}$，$L \le _L L'$。

$\text{Circuit-Eval}$ 是$\textbf{PC}$的。单调电路也是$\textbf{PC}$的。

$$
\textbf{NC} ^1 \subseteq \textbf{L} \subseteq \textbf{NL} \subseteq \textbf{NC} ^2...\textbf{NC} ^i \subseteq \textbf{P}
$$

  • $\textbf{NL} \in \textbf{NC} ^2$，因为$\text{Reachability} \in \textbf{NC} ^2$。

Hastad Switching Lemma

$$
\textbf{NC} ^0 \subsetneq \textbf{AC} ^0 \subsetneq \textbf{NC} ^1
$$

有些函数无法用常数高度的电路计算。即常数高度的电路严格弱于对数高度的电路。

该引理专门用于研究电路复杂性的下界。

Minterm：$x _1,...,x _n$组成的集合，可取非，可$\land$。

$f$的极小项：$f _\rho (x _1,..., x _n)$恒等于1且不存在$\text{sub}-\rho$。

极小项就是合取项。