回路計算量(circuit complexity)とは、ブール関数 $\{0,1\}^n\to\{0,1\}$ を $\wedge,\vee,\neg$ の門からなる論理回路で計算するときに必要な門の個数(大きさ)や深さのことで、入力の長さごとに回路を用意する非一様な計算のモデルで難しさを測る。どの関数も大きさ $3\cdot2^n-4$ 以下の回路をもつが、$n\ge4$ ではほとんどの関数は大きさ $2^n/(4n)$ を超える回路を要する(Shannon)。多項式時間で判定できる言語は多項式の大きさの回路の族をもち($\mathrm{P}\subset\mathrm{P/poly}$)、NP がそうなら多項式階層は第 2 層に潰れる(Karp–Lipton)。偶奇の関数は深さが定数で多項式の大きさの回路では計算できない。
回路計算量(circuit complexity)は、ブール関数 $\{0,1\}^n\to\{0,1\}$ を計算する論理回路の大きさ(門の個数)や深さによって、関数の計算の難しさを測る分野である。Turing機械 は 1 台の機械ですべての長さの入力を扱うのに対し、回路は入力の長さ $n$ ごとに別のものを用意する。この違いのため、回路の族で判定できる言語のクラスは、判定不能な言語まで含みうる。
それでも回路が重要なのは、多項式時間で判定できる言語は多項式の大きさの回路の族で判定できる($\mathrm{P}\subset\mathrm{P/poly}$)からである。したがって、ある NP の言語に多項式の大きさの回路の族がないことを示せば、$\mathrm{P}\ne\mathrm{NP}$ が従う(P対NP問題)。回路は計算の中身を有限の組合せ的な対象として見せるので、Turing 機械より扱いやすいと期待された。
この記事では、論理回路と回路計算量を定義し、どのブール関数も大きさ $3\cdot2^n$ 未満の回路をもつこと、それでもほとんどのブール関数は大きさ $2^n/(4n)$ を超える回路を要すること(Shannon の数え上げ)、$\mathrm{P}\subset\mathrm{P/poly}$、Karp–Lipton の定理を証明する。深さが定数の回路の族のクラス $\mathrm{AC}^0$ については、偶奇の関数の深さ 2 の下界を証明し、偶奇の関数が $\mathrm{AC}^0$ に属さないこと(Furst–Saxe–Sipser、Ajtai、Håstad)などの下界は主張として述べる。
$n\ge1$ とする。$n$ 入力の論理回路 $C$ とは、有向閉路をもたない有限の有向グラフであって、頂点が次の 2 種類に分かれ、出力の頂点が $1$ つ指定されたものである。
AB07 Definition 6.1(p. 102)は入力の頂点も大きさに数える。違いは $n$ だけで、以下の結論には影響しない。
$f\colon\{0,1\}^n\to\{0,1\}$ を計算する回路の大きさの最小値を $f$ の 回路計算量 という。$s\colon\mathbb{N}\to\mathbb{N}$ について、言語 $L\subset\{0,1\}^*$ が $\mathrm{SIZE}(s)$ に属するとは、回路の族 $\{C_n\}_{n\ge1}$ があって、$C_n$ は $n$ 入力で $|C_n|\le s(n)$ であり、すべての $x\in\{0,1\}^n$ について $x\in L\iff C_n(x)=1$ となることをいう。
$$
\mathrm{P/poly}:=\bigcup_{c\ge1}\mathrm{SIZE}(n^c)
$$
とおく(AB07 Definitions 6.2–6.3、p. 103)。
$n\ge1$ とする。どの $f\colon\{0,1\}^n\to\{0,1\}$ も、大きさ $3\cdot2^n-4$ 以下の回路で計算できる。
$n$ についての帰納法で示す。$n=1$ では、関数は $x_1$(門 $0$ 個)、$\neg x_1$($1$ 個)、定数 $0=x_1\wedge\neg x_1$、定数 $1=x_1\vee\neg x_1$($2$ 個)の 4 つで、どれも $2=3\cdot2-4$ 個以下である。
$n\ge2$ とし、$b\in\{0,1\}$ について $f_b(x_1,\dots,x_{n-1}):=f(x_1,\dots,x_{n-1},b)$ とおく。$f=(x_n\wedge f_1)\vee(\neg x_n\wedge f_0)$ である。帰納法の仮定から $f_0,f_1$ をそれぞれ $3\cdot2^{n-1}-4$ 個以下の門で計算し、門 $\neg x_n$、2 個の $\wedge$、1 個の $\vee$ を足すと、門は $2(3\cdot2^{n-1}-4)+4=3\cdot2^n-4$ 個以下である。$\square$
上界は $2^n$ の定数倍で、指数関数的である。次の定理は、ほとんどの関数でこれがほぼ避けられないことを示す。
$n\ge4$ とし、$s:=\lfloor2^n/(4n)\rfloor$ とおく。$n$ 変数のブール関数 $2^{2^n}$ 個のうち、大きさ $s$ 以下の回路で計算できるものの割合は $2^{\,n+1-3\cdot2^{n-3}}$ 以下である。とくに、回路計算量が $2^n/(4n)$ を超える $n$ 変数のブール関数があり、その割合は $n\to\infty$ で $1$ に近づく。
大きさをちょうど $s$ にそろえる. $n\ge4$ なら $s\ge1$ である。大きさ $s$ 未満の回路には、使わない門 $x_1\wedge x_1$ を足して大きさをちょうど $s$ にできる。計算する関数は変わらない。よって、大きさ $s$ 以下の回路で計算できる関数の個数は、大きさちょうど $s$ の回路で計算できる関数の個数以下である。
書き方の個数. 大きさ $s$ の回路の頂点を、入力の頂点を $1,\dots,n$、門を $n+1,\dots,n+s$ と番号づける。回路は、各門の印(3 通り)と入ってくる 2 本の辺の元の頂点($\neg$ では 1 本目だけを使う。各 $n+s$ 通り)、および出力の頂点($n+s$ 通り)を並べた列で決まる。このような列の個数は
$$
(n+s)\big(3(n+s)^2\big)^s\le\big(3(n+s)\big)^{2s+1}
$$
以下である。閉路をもつなど回路にならない列も数えているが、上からの評価としては差し支えない。各列は高々 $1$ つの関数を計算するので、大きさ $s$ 以下の回路で計算できる関数は $\big(3(n+s)\big)^{2s+1}$ 個以下である。
評価. $n\ge4$ では $n\le2^n/4$、$s\le2^n/(4n)\le2^n/4$ なので $n+s\le2^{n-1}$ で、$3(n+s)\le3\cdot2^{n-1}< 2^{n+1}$ である。また $2s+1\le2^n/(2n)+1$ である。よって関数の個数は
$$
2^{(n+1)(2s+1)}\le2^{\,2^n(n+1)/(2n)+n+1}
$$
以下で、$2^{2^n}$ 個の関数の中での割合は
$$
2^{\,n+1-2^n\cdot\frac{n-1}{2n}}
$$
以下である。$n\ge4$ では $\frac{n-1}{2n}\ge\frac38$ なので、割合は $2^{\,n+1-\frac38\cdot2^n}=2^{\,n+1-3\cdot2^{n-3}}$ 以下である。$n=4$ ではこれは $1/2$ で、$n$ が大きくなると $0$ に近づく。$\square$
この議論は、条件を満たす関数が ある ことを示すだけで、具体的な関数を与えない。NP に属する具体的な言語について知られている一般の回路の大きさの下界は、2007 年の時点で入力の長さ $n$ の定数倍程度にとどまっていた(AB07 §6.3、p. 107 と 13 章の冒頭、p. 235)。同書の Theorem 6.15 は、$n\ge100$ のとき大きさ $2^n/(10n)$ についての同じ形の主張である(p. 107)。
ここでの Turing機械 は、テープ 1 本で左端があり、ヘッドが左端で左へ動こうとするとその場にとどまるものとする。テープが複数本の機械は、時間 $T(n)$ の計算を 1 本のテープの機械で時間 $O(T(n)^2)$ で模倣できる(この記事では証明しない)。また、機械は受理状態か拒否状態に入ったら、以後は状態もテープも変えないものとする。
$T(n)\ge n$ とし、テープ 1 本の Turing 機械 $M$ が長さ $n$ のどの入力でも $T(n)$ 歩以内に止まるとする。このとき定数 $c_M$ があって、各 $n$ について、大きさ $c_M\,(T(n)+1)^2$ 以下の $n$ 入力の回路 $C_n$ で、すべての $x\in\{0,1\}^n$ について $C_n(x)=1\iff M$ が $x$ を受理する、となるものがある。とくに $\mathrm{P}\subset\mathrm{P/poly}$ である。
$T:=T(n)$ とおく。$T$ 歩の間にヘッドはセル $0,\dots,T$ の外へ出ない。$M$ のテープ記号の集合を $\Gamma$、状態の集合を $Q$ とし、セルの 中身 を、テープ記号 $a\in\Gamma$ と「ヘッドがここになければ $\ast$、あれば状態 $q\in Q$」の組 $(a,\ast)$ または $(a,q)$ で表す。中身は有限個なので、$k$ ビットの列で符号化する($k$ は $M$ だけで決まる)。時刻 $t$ の 行 とは、時刻 $t$ におけるセル $0,\dots,T$ の中身の列のことで、$T+1$ 個の $k$ ビットの区画からなる。
局所性. 時刻 $t+1$ のセル $j$ の中身は、時刻 $t$ のセル $j-1,j,j+1$ の中身だけで決まる。実際、ヘッドが $j-1,j,j+1$ のどこにもなければ記号は変わらずヘッドも来ない。どこかにあれば、その状態と読んでいる記号から遷移が決まり、セル $j$ の新しい記号と、ヘッドが $j$ に来るかどうか、来るならその状態が決まる。左端 $j=0$ では「セル $-1$」として、どの中身の符号とも異なる $k$ ビットの語(左端の印。そのぶん $k$ を大きくとる)を定数として与え、左端でヘッドが左へ動こうとするときの規則もこの局所の規則に含める。右端 $j=T$ でも同じく定数を補う。こうして、$M$ だけで決まる関数 $g\colon\{0,1\}^{3k}\to\{0,1\}^k$ で、時刻 $t+1$ のセル $j$ の符号が時刻 $t$ のセル $j-1,j,j+1$ の符号の $g$ の値になるものがある。受理・拒否状態で止まるという約束も $g$ に含める。
回路の組み立て. $g$ の $k$ 個の出力の各ビットは $3k$ 変数のブール関数なので、prop-circ-upper により $3\cdot2^{3k}-4$ 個以下の門で計算できる。よって $g$ は大きさ $c_g:=k(3\cdot2^{3k}-4)$ 以下の回路 $G$ で計算できる。定数 $0,1$ は門 $x_1\wedge\neg x_1$、$x_1\vee\neg x_1$ で作る。
組み立ては Cook–Levinの定理 の証明と同じ考え方である。$C_n$ は $n$ から機械的に書き出せるので、族 $\{C_n\}$ は一様である。逆に、$n$ から $C_n$ を対数領域で書き出せる多項式の大きさの回路の族で判定できる言語は $\mathrm{P}$ に属し、一様な回路の族は $\mathrm{P}$ をちょうど特徴づける(AB07 Theorem 6.7、p. 104。この記事では証明しない)。
NP の言語がすべて多項式の大きさの回路の族をもつとすると何が起きるか。答えは 戸田の定理(計算量) にも現れる多項式階層で述べられる。
言語 $L$ が $\Sigma_2$ に属するとは、多項式 $p$ と多項式時間の機械 $M$ があって、すべての $x$ について
$$
x\in L\iff\exists u\in\{0,1\}^{p(|x|)}\ \forall v\in\{0,1\}^{p(|x|)}\ M(x,u,v)=1
$$
となることをいう。$\forall$ と $\exists$ を入れ替えたものを $\Pi_2$ とする。$L\in\Sigma_2\iff\overline{L}\in\Pi_2$ である。同様に量化子を $i$ 回交代させたクラス $\Sigma_i$ の和集合を 多項式階層 $\mathrm{PH}$ という(AB07 Definition 5.4、p. 93)。
$\Sigma_i=\Pi_i$ なら $\mathrm{PH}=\Sigma_i$ となる(AB07 Theorem 5.6、p. 93。この記事では証明しない)。
$\mathrm{NP}\subset\mathrm{P/poly}$ ならば $\Sigma_2=\Pi_2$ で、したがって $\mathrm{PH}=\Sigma_2$ である(AB07 Theorem 6.13、pp. 106–107)。
$\Pi_2\subset\Sigma_2$ を示せば十分である。実際そのとき、$L\in\Sigma_2$ なら $\overline{L}\in\Pi_2\subset\Sigma_2$ なので $L\in\Pi_2$ となる。
$L\in\Pi_2$ とし、$x\in L\iff\forall u\,\exists v\ M(x,u,v)=1$($|u|=|v|=p(|x|)$)と書く。$n:=|x|$、$m:=p(n)$ とおく。$1\le k\le m$ と $w\in\{0,1\}^m$ について「$v_1\cdots v_k=w_1\cdots w_k$ となる $v\in\{0,1\}^m$ で $M(x,u,v)=1$ となるものがある」という性質をもつ組 $(x,u,k,w)$($k$ は $m$ に合わせた桁数の 2 進で、全体を $n$ だけで決まる長さに符号化する)の言語 $L'$ は NP に属する。仮定から $L'$ を判定する多項式の大きさの回路 $E_n$ がある。
出力が $m$ 個の回路 $D_n$(def-circ-circuit で出力の頂点を $m$ 個の列として指定したもの)を次のように作る。$k=1,\dots,m$ の順に、$w=v_1\cdots v_{k-1}10\cdots0$ として $E_n(x,u,k,w)$ を計算し、その値を $v_k$ とする。$E_n$ の写しを $m$ 個つなげるので、$D_n$ の大きさは $n$ の多項式 $q(n)$ でおさえられる。ある $v$ で $M(x,u,v)=1$ となるなら、帰納法で「$v_1\cdots v_k$ は解に延ばせる」が各 $k$ で保たれ、$D_n(x,u)$ は解である。
大きさ $q(n)$ 以下の回路は、出力の頂点を $m$ 個並べることを除いて thm-circ-shannon の証明の列と同じ書き方で、長さ $r(n)=O(q(n)\log q(n))$ の文字列に書ける。すると
$\displaystyle x\in L\iff\exists d\in\{0,1\}^{r(n)}\ \forall u\in\{0,1\}^{m}\ \big(d\text{ は回路 }D\text{ を表し }M(x,u,D(x,u))=1\big)$
が成り立つ。$\Rightarrow$ は $d$ を $D_n$ の記述とすればよい。$\Leftarrow$ は、各 $u$ について $D(x,u)$ が $\exists v$ の証拠になる。右辺の括弧の中は、回路を評価して $M$ を走らせるだけなので多項式時間で判定できる。よって $L\in\Sigma_2$ である。$\square$
対偶をとると、$\mathrm{PH}$ が第 2 層で潰れないと信じるかぎり、NP の言語、たとえば充足可能性問題は多項式の大きさの回路の族をもたない。ここで $\mathrm{P}$ と NP の分離から一様性を取り除いた $\mathrm{NP}\not\subset\mathrm{P/poly}$ は、$\mathrm{P}\ne\mathrm{NP}$ より強い予想である(AB07 §6.3、p. 107)。
一般の回路の下界は弱いままだが、回路に制限を課すと強い下界が証明できる。代表は深さの制限である。
$\wedge,\vee$ の門の入ってくる辺の本数を制限しない回路を考える。言語 $L$ が $\mathrm{AC}^0$ に属するとは、定数 $c,d$ と回路の族 $\{C_n\}$ があって、$C_n$ は大きさ $n^c$ 以下、深さ $d$ 以下で、長さ $n$ の入力について $L$ を判定することをいう。
AB07 Definitions 6.21–6.22(pp. 109–110)は族に対数領域で書き出せるという一様性も課す。以下の下界は一様性のない族についての主張で、そのほうが強い。
入ってくる辺の本数を制限しなければ、論理式 の 加法標準形(DNF。リテラル $x_i,\neg x_i$ の $\wedge$ である 項 の $\vee$)は深さ $2$($\neg$ を入力側に寄せて数えない場合)の回路である。どのブール関数も、値が $1$ になる点ごとにその点だけで $1$ になる項を作れば DNF で書ける。偶奇の関数ではこれが最良である。
$n\ge1$ とする。$\mathrm{PAR}_n$ を DNF で表すと、項は $2^{n-1}$ 個以上必要である。
$\mathrm{PAR}_n=T_1\vee\cdots\vee T_r$ とする。$x_i$ と $\neg x_i$ を両方含む項は恒等的に $0$ なので、取り除いても値は変わらない。そこで、どの項も $1$ になる点をもつとしてよい。
項 $T$ がある変数 $x_i$ を含まない($x_i$ も $\neg x_i$ も現れない)とする。$T(a)=1$ となる $a$ をとり、$a$ の第 $i$ 成分だけを反転した点を $a'$ とすると、$T$ は $x_i$ によらないので $T(a')=1$ である。よって $\mathrm{PAR}_n(a)=\mathrm{PAR}_n(a')=1$ となるが、$a$ と $a'$ は $1$ の個数の偶奇が異なるので矛盾である。
したがってどの項もすべての変数を含み、ちょうど $1$ 点でだけ $1$ になる。$\mathrm{PAR}_n$ が $1$ になる点は $2^{n-1}$ 個あり、各点はどれかの項で $1$ にならなければならないので、$r\ge2^{n-1}$ である。$\square$
同じ議論で、連言標準形(CNF)でも節が $2^{n-1}$ 個以上必要である($\neg\mathrm{PAR}_n$ も同じ形をしているので、そのド・モルガン双対を考えればよい)。深さを $3,4,\dots$ と上げても多項式の大きさでは足りない、というのが次の定理である。
$\{x\in\{0,1\}^*:x\text{ の }1\text{ の個数が奇数}\}$ は $\mathrm{AC}^0$ に属さない(Furst–Saxe–Sipser、Ajtai。AB07 Theorem 13.1、p. 235。この記事では証明しない)。
証明の中心は Håstad の スイッチング補題 である。入力の変数の一部をランダムに選んでランダムな値に固定する(ランダムな制限)と、項の幅が小さい DNF は、高い確率で節の幅が小さい CNF でも書ける関数に変わる(AB07 Lemma 13.2、p. 236)。DNF と CNF が入れ替えられると、回路の下の 2 層の $\vee$ と $\wedge$ を同じ種類にそろえて 1 層にまとめられ、深さが 1 減る。これを深さの回数くり返すと、まだ固定されていない変数が多く残っているのに定数か浅い決定木で決まる関数になる。一方、偶奇の関数は制限しても残った変数の偶奇の関数のままなので、矛盾する。
ほかの制限でも、次の下界が知られている(いずれもこの記事では証明しない)。
次の表の各行は、上の結論が使っている仮定を 1 つだけ外した例である。
| 外す仮定 | 例 | 成り立たなくなる結論 |
|---|---|---|
| 回路の族が機械的に書き出せる(一様性) | 判定不能な $L\subset\{1^n\}$ を、$n$ ごとに $x_1\wedge\cdots\wedge x_n$ か $x_1\wedge\neg x_1$ で判定する(ex-circ-examples) | 多項式の大きさの回路の族で判定できる言語は $\mathrm{P}$ に属する(一様な族なら成り立つ) |
| 大きさが多項式 | どの言語も大きさ $3\cdot2^n-4$ の族で判定できる(prop-circ-upper) | $\mathrm{P/poly}$ に属さない言語がある($n$ ごとに回路計算量が $2^n/(4n)$ を超える関数を選べば得られる) |
| 門の種類が有限で入ってくる辺が高々 2 本 | $f$ そのものを 1 個の門として許すと、どの $f$ も大きさ $1$ | ほとんどの関数の回路計算量は $2^n/(4n)$ を超える(thm-circ-shannon) |
| 深さが定数 | $\mathrm{PAR}_n$ は大きさ $4(n-1)$、深さ $O(\log n)$(ex-circ-examples) | 偶奇の関数は多項式の大きさで計算できない(thm-circ-parity-ac0) |
最後の行は、$\mathrm{AC}^0$ の下界が深さの制限から来ていて、大きさだけの問題ではないことを示す。3 行目では、Shannon の数え上げは回路の書き方の個数が $2^{O(s\log s)}$ にとどまることだけを使っていた。門の種類が無限にあると、この個数の評価が成り立たない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する