Article Index

电路复杂度学习笔记

简述

对于某些电路，我们用一些特征来判断它的 复杂度。

$\mathsf{AC^0}$ 电路
由多项式大小，常数深度，无限扇入（fan-in）的电路系（circuit families）描述的语言。非门只允许出现在输入处。
$\mathsf{ACC^0}\left[m\right]$ 电路
由多项式大小，常数深度，无限扇入（fan-in）和 $\mathsf{MOD}_m$ 门的电路系（circuit families）描述的语言。
$\mathsf{ACC^0}$ 电路
$\mathsf{ACC^0} = \bigcup_{m>1}\mathsf{ACC^0}\left[m\right]$
$\mathsf{TC^0}$ 电路
由多项式大小，常数深度，无限扇入（fan-in）和 MAJORITY 门的电路系（circuit families）描述的语言。
$\mathsf{NC^m}$ 电路
由多项式大小，$\mathcal O\left(\log^m n\right)$ 深度，无限扇入（fan-in）的电路系（circuit families）描述的语言。
$\mathsf {P / poly}$ 电路
由多项式大小的电路系（circuit families）描述的语言。

包含关系如下

$$\mathsf{AC^0} \subsetneq \mathsf{ACC^0} \subseteq \mathsf{TC^0} \subseteq \mathsf{NC^1} \subseteq \mathsf{P / poly}$$

我们想用 MAJORITY 门来模拟 $\mathsf{MOD}_m$ 门，假设 $n$ 是奇数（如果是偶数就添加一个 $0$ 输入即可）

$$\boxed{\mathsf{MOD_m}\left(x_1, \ldots, x_n\right) = \bigvee\left\{\#k\left(x_1, \ldots, x_n\right) : 0 \leq k \leq n, m \mid k\right\}}$$

其中 $\#k$ 仅在恰好输入中有 $k$ 个 $1$ 时输出 $1$。

$$\boxed{\#k\left(x_1, \ldots, x_n\right) = \mathsf{Th}_k\left(x_1, \ldots, x_n\right) \land \neg \mathsf{Th}_{k + 1}\left(x_1, \ldots, x_n\right)}$$

其中 $\mathsf{Th}_k\left(x_1, \ldots, x_n\right)$ 仅在输入中至少有 $k$ 个 $1$ 时输出 $1$。

如果 $k \leq \left(n - 1\right) / 2$：

$$\boxed{\mathsf{Th}_k\left(x_1, \ldots, x_n\right) = \mathsf{MAJ}\left(x_1, \ldots, x_n, 1, \ldots, 1\right)}$$

其中，额外的 $1$ 有 $n - 2k + 1$ 个。

否则 $k \geq (n + 1) / 2$：

$$\boxed{\mathsf{Th}_k\left(x_1, \ldots, x_n\right) = \mathsf{MAJ}\left(x_1, \ldots, x_n, 0, \ldots, 0\right)}$$

其中，额外的 $0$ 有 $2k - n - 1$ 个。

仍然是多项式大小，常数深度。

我们想用对数深度的电路来模拟 MAJ 门。一个很简单的想法是在第 $i$ 层把两个 $i$ 位数相加，判断结果是否大于一半即可，一共对数层。

如果你在加法时使用行波进位加法器（Ripple-Carry Adder, RCA），那么深度是 $\mathcal O\left(\log^2 n\right)$ 的，于是你将得到一个 $\mathsf{NC^2}$ 的电路。

使用超前进位加法器（Carry-Lookahead Adder, CLA），即可构造出 $\mathsf{NC^1}$ 电路。