回路計算量 | 計算理論 | 天游ヶ丘数理学院

1 Boolean 回路と二つの資源

定義 1.1. $n$ 入力の Boolean 回路 (Boolean circuit) $C$ は、次の印をもつ頂点からなる有限有向非巡回グラフであり、出力頂点を一つ指定したものである。

入力頂点 $x_1,\ldots,x_n$ と定数頂点 $0,1$ の入次数は $0$ である。
NOT ゲートの入次数は $1$ である。
AND ゲートと OR ゲートの入次数は $2$ である。

辺はゲートへの入力を表す。同じ頂点から出る辺の本数、すなわち fan-out は制限しない。入力 $x=(x_1,\ldots,x_n)\in\{0,1\}^n$ を入力頂点へ割り当て、トポロジカル順序に従って各ゲートを評価したときの出力頂点の値を $C(x)$ と書く。

$C$ の入力頂点を除く頂点数をサイズ (circuit size) $|C|$ とする。入力頂点と定数頂点の深さを $0$ とし、ゲート $g$ の深さを

1+\max\{\text{$g$ の入力となる頂点の深さ}\}

とする。出力頂点の深さを回路の深さ (circuit depth) $\operatorname{depth}(C)$ とする。

この定義は有界 fan-in を固定している。fan-in が入力長とともに増える AND または OR を一ゲートと数える別の規約では、特に深さの値が変わるため、二つの規約を混同してはならない。

命題 1.2. 回路 $C$ と入力 $x$ の組のうち $C(x)=1$ となるものからなる言語を 回路値問題という。回路値問題は $\mathsf P$ に属する。さらに、同じ手続きによって $C(x)$ の値を計算することができる。

証明. 有向グラフをトポロジカル整列し、その順序で各頂点の値を一度だけ計算する。NOT、AND、OR の fan-in は高々 $2$ なので、整列後の各頂点の評価には定数時間しか要しない。トポロジカル整列も評価も頂点数と辺数の和に比例する時間で実行することができる。頂点と辺は入力記述に含まれるため、全時間は入力記述長の多項式である。従って、この手続きは回路値を決定する多項式時間機械である。▨

例 1.3 (サイズと深さ). $n\ge 1$ 個の入力の AND を考える。左から一つずつ AND を取る回路は、 $n\ge2$ ではサイズ $n-1$ 、深さ $n-1$ である。一方、入力を二群に分ける操作を再帰的に行い、各群の AND を並列に計算する二分木型の回路は、サイズ $n-1$ 、深さ $\lceil\log_2 n\rceil$ である。従って、サイズが同じ二つの回路でも深さは異なり得る。

2 回路族と P 一様性

定義 2.1. 各 $n\ge0$ に対して $n$ 入力 Boolean 回路 $C_n$ を一つ対応させた列 $\mathcal C=(C_n)_{n\ge0}$ を回路族 (circuit family) という。回路族 $\mathcal C$ が言語 $L\subseteq\{0,1\}^*$ を決定するとは、全ての $n$ と $x\in\{0,1\}^n$ について

C_n(x)=1\quad\Longleftrightarrow\quad x\in L

が成り立つことをいう。

定数 $c,k>0$ が存在し、全ての $n$ について

|C_n|\le c(n+1)^k

となるとき、 $\mathcal C$ は多項式サイズ (polynomial size) である。深さについても同様に、ある多項式を全ての入力長に共通の上界として取る。

回路記述では、頂点をトポロジカル順に並べ、各頂点について印と入力元の頂点番号を二進表記する。この規約を固定すると、回路の完全な記述から回路を復元することができ、記述長は回路の頂点数と辺数の多項式である。

定義 2.2. 回路族 $\mathcal C=(C_n)_{n\ge0}$ が P 一様 (P-uniform) であるとは、ある決定性 Turing 機械 $G$ と多項式 $q$ が存在し、全ての $n$ について $G$ が入力 $1^n$ から $C_n$ の完全な記述を $q(n+1)$ 時間以内に出力して停止することをいう。 $G$ を $\mathcal C$ の一様性生成器 (uniformity generator) という。

生成器は入力値 $x$ ではなく入力長 $n$ だけを受け取る。従って、生成器が出力するのは特定の入力に対する答えではなく、長さ $n$ の全入力に共通して使用する回路である。また、一段で高々定数個の記号しか出力することができないため、P 一様な回路族の回路記述長とサイズは自動的に多項式で抑えられる。P 一様性から多項式サイズ性が従う場合でも、次の定理では Turing 機械から構成する回路のサイズを直接数える。

3 多項式時間計算を回路へ展開する

定理 3.1. 言語 $L\subseteq\{0,1\}^*$ について、次の二条件は同値である。

$L\in\mathsf P$ である。
$L$ を決定する P 一様な多項式サイズ Boolean 回路族が存在する。

証明方針は、前向きでは一方向無限テープ上の有界時間計算を時刻と位置の格子へ展開し、各セル記号を one-hot 符号で表すことである。左端セルには境界専用の局所関数を用い、内点と有限窓の右端には通常の局所関数を用いる。各局所関数の真理値表を定数サイズの部分回路にして、初期配置から最終配置までを時刻順に接続する。逆向きでは、一様性生成器が出力した回路をトポロジカル順に評価する。

証明. 最初に $L\in\mathsf P$ とする。§E15.10 定義 1.4と§E15.10 系 4.2により、 $L$ を決定する機械の作業テープを一本にすることができる。この機械の読取り専用入力テープと作業テープの有限使用部分を、一つのテープ上で区切り記号と二つのヘッド印を用いて表す。元の一段ごとに符号全体を有限回走査すれば、入力ヘッドが読む記号と作業ヘッドが読む記号を有限制御へ保存し、両ヘッドの移動と書込みを反映することができる。元の計算が多項式時間なら、符号長も走査回数も入力長の多項式であるため、この一テープ模倣も多項式時間である。この模倣を、入力 $x$ が計算開始時に唯一のテープの左端から置かれる一テープ決定性機械 $M$ として実装する。区切り付きの内部符号を用意する初期化と、その後の模倣を合わせても多項式時間である。 $M$ のテープは位置 $0,1,\ldots$ からなる一方向無限テープであり、位置 $0$ で左移動を命じられたヘッドは位置 $0$ にとどまる。停止後は同じ受理配置または拒否配置にとどまる遷移を加える。整数 $c,d\ge1$ が存在して、初期化と模倣のオーバーヘッドを含む全計算が

T(n)=c(n+1)^d

段以内に停止するように $c,d$ を取る。

$M$ のテープアルファベットを $\Gamma$ 、状態集合を $Q$ とする。テープの一マスには、ヘッドがない場合の記号 $a\in\Gamma$ 、またはヘッドと状態を併せた記号 $(q,a)\in Q\times\Gamma$ のいずれかを記録する。従って、一マスの内容は固定有限集合

A=\Gamma\mathbin{\sqcup}(Q\times\Gamma)

の要素で表すことができる。位置 $-1$ には $A$ に属さない固定左端記号 $\triangleleft$ があるものとみなす。入力 $x=x_1\cdots x_n$ に対し、 $n>0$ なら初期位置 $0$ の記号を $(q_0,x_1)$ 、位置 $1,\ldots,n-1$ の記号を順に $x_2,\ldots,x_n$ とし、それ以外の位置を空白記号 $\sqcup$ とする。 $n=0$ なら初期位置 $0$ の記号を $(q_0,\sqcup)$ とし、それ以外の位置を空白とする。

一段でヘッドは高々一マス移動するため、

W(n)=n+T(n)+1

と置けば、位置 $0,\ldots,W(n)-1$ は初期入力の全セルと、時刻 $0$ から $T(n)$ までにヘッドが訪れる全セルを含む。特に $t<T(n)$ ではヘッド位置が高々 $t<T(n)\le W(n)-1$ であるため、位置 $W(n)$ は空白のままである。

内点 $j\ge1$ について、決定性遷移規則から、時刻 $t+1$ の位置 $j$ の内容は、時刻 $t$ の位置 $j-1,j,j+1$ の内容だけで決まる。実際、ヘッドが中央または隣接位置になければ記号は変わらず、ヘッドが三つの位置のいずれかにあれば遷移規則が書込み、状態、および移動先を一意に定める。正当な配置には現れない三つ組に対する値は任意に固定する。従って、固定した有限関数

F\colon A^3\longrightarrow A

が存在する。

左端位置 $0$ の次の内容は、現在の位置 $0,1$ の内容と、左端での左移動を位置 $0$ にとどめる規約から一意に定まる。正当な配置には現れない二つ組に対する値を任意に固定し、左端専用の有限関数を

F^{\mathrm L}\colon A^2\longrightarrow A

とする。固定記号 $\triangleleft$ は、この関数が通常の三セル更新とは異なる左端更新を表すことを明示する。有限窓の右端位置 $W(n)-1$ では、位置 $W(n)$ の内容を固定空白 $\sqcup$ として $F$ を用いる。

各時刻 $0\le t\le T(n)$ 、位置 $0\le j<W(n)$ 、記号 $a\in A$ に対して、時刻 $t$ の位置 $j$ が $a$ であることを表す線 $z_{t,j,a}$ を置く。各位置の線は、正当な計算では一つの要素を表す one-hot 符号である。 $n>0$ の位置 $0$ では、 $(q_0,0)$ と $(q_0,1)$ に対応する線を $\operatorname{NOT}x_1$ と $x_1$ から作る。位置 $1,\ldots,n-1$ では、記号 $0,1$ に対応する線を $\operatorname{NOT}x_{j+1}$ と $x_{j+1}$ から作る。 $n=0$ では位置 $0$ の $(q_0,\sqcup)$ に対応する線を定数 $1$ とする。 $n>0$ では位置 $n,\ldots,W(n)-1$ を空白とし、 $n=0$ では位置 $1,\ldots,W(n)-1$ を空白とする。定数で指定した各位置では、指定した初期記号以外の線を定数 $0$ とする。また、入力ビットから指定した位置 $0,\ldots,n-1$ でも、上で挙げた二本以外の全ての線を定数 $0$ とする。従って、 $n=0$ を含む全ての入力長で、初期層の各位置は $A$ の要素をちょうど一つ表す one-hot 符号になる。

$A$ は $M$ ごとに固定されているので、内点 $1\le j<W(n)-1$ では、各 $a\in A$ について

F(u,v,w)=a

となる有限個の三つ組を列挙し、それぞれの一致条件を AND で結び、得られた項を OR で結ぶことができる。この真理値表の回路化により $z_{t+1,j,a}$ を計算する定数サイズ・定数深さの部分回路を得る。

左端 $j=0$ では

F^{\mathrm L}(v,w)=a

となる有限個の二つ組を列挙し、位置 $0,1$ の一致条件から $z_{t+1,0,a}$ を計算する境界専用の部分回路を置く。右端 $j=W(n)-1$ では

F(u,v,\sqcup)=a

となる有限個の二つ組を列挙し、位置 $W(n)-2,W(n)-1$ の一致条件から右端の次状態を計算する。三種類の部分回路はいずれも定数サイズ・定数深さである。全ての $t<T(n)$ について、位置の種類に応じた固定テンプレートを置く。

初期配置の線が $M$ の初期配置を表すことは構成から従う。時刻 $t$ の線が正しい配置を表すと仮定すると、左端では $F^{\mathrm L}$ 、内点と右端では $F$ の定義により、時刻 $t+1$ の線は $M$ の一意な次配置を表す。従って、時刻に関する帰納法により、最終層は $M$ の時刻 $T(n)$ の配置を表す。受理状態を含む記号に対応する最終層の線を二分木型の OR で結んで出力とする。停止配置は変化しないようにしたため、この出力は $M$ が $x$ を受理するとき、かつそのときに限り $1$ となる。

各時刻・位置には $|A|$ 本の線と定数個のゲートしかなく、 $|A|$ は $n$ に依存しない。従って、得られた回路 $C_n$ のサイズは

O\bigl(T(n)W(n)\bigr)+O(W(n)) =O\bigl(T(n)(n+T(n))\bigr)

であり、多項式である。各遷移層の深さは定数であるため、深さも $O(T(n)+\log W(n))$ である。

最後に一様性を示す。入力 $1^n$ を受け取った生成器は、 $T(n)$ と $W(n)$ を計算し、時刻、位置、記号の三重の反復によって、上で述べた固定テンプレートと配線番号を順に出力する。出力するゲート数は $O(T(n)W(n))$ 、各番号の長さは $O(\log(T(n)W(n)+2))$ である。二進整数の計算を含めても、生成時間は

O\bigl(T(n)W(n)\operatorname{polylog}(T(n)W(n)+2)\bigr)

の多項式で抑えられる。従って、 $(C_n)_{n\ge0}$ は P 一様である。

逆に、 $L$ を決定する P 一様な回路族 $(C_n)_{n\ge0}$ と生成器 $G$ が存在するとする。入力 $x\in\{0,1\}^n$ に対し、最初に $G(1^n)$ を実行して $C_n$ の完全な記述を得る。生成時間を $q(n+1)$ とすれば、出力記述長も $q(n+1)$ 以下である。次に命題 1.2の手続きで $x$ を入力した $C_n$ を評価する。評価時間は回路記述長と $n$ の多項式であり、従って全時間も $n$ の多項式である。回路族が $L$ を決定するため、この機械は $x\in L$ の場合に、かつその場合に限り受理する。従って $L\in\mathsf P$ である。▨

前向きの構成が作るのは、入力 $x$ ごとの回路ではなく、変数 $x_1,\ldots,x_n$ を残した一つの回路 $C_n$ である。この区別によって、同じ長さの全ての入力に共通の回路を用いるという回路族の要件が満たされる。また、局所遷移の部分回路が定数サイズである理由は、機械 $M$ の状態集合とテープアルファベットを入力長によらず固定したことにある。

4 非一様な P/poly

定義 4.1. 言語 $L\subseteq\{0,1\}^*$ が P/poly (P/poly) に属するとは、 $L$ を決定する多項式サイズ Boolean 回路族 $(C_n)_{n\ge0}$ が存在することをいう。一様性生成器の存在は要求しない。このような言語のクラスを $\mathsf{P/poly}$ と書く。

定理 3.1から $\mathsf P\subseteq\mathsf{P/poly}$ が従う。しかし、P/poly の回路 $C_n$ は入力長ごとに独立に選ぶことができ、回路列そのものを有限のアルゴリズムから生成することができるとは限らない。

命題 4.2. 任意の集合 $S\subseteq\mathbb N$ に対して、単項言語

L_S=\{1^n:n\in S\}

は $\mathsf{P/poly}$ に属する。特に、決定不能な言語も $\mathsf{P/poly}$ に属し得る。

証明. 各 $n$ について、 $n\in S$ なら入力 $x_1,\ldots,x_n$ の AND を出力し、 $n\notin S$ なら定数 $0$ を出力する回路 $C_n$ を選ぶ。 $n=0$ では空語を $1^0$ とみなし、 $0\in S$ かどうかに応じた定数回路を選ぶ。二分木型の AND を用いると $|C_n|\le n+1$ であり、 $C_n$ は $1^n$ だけを、かつ $n\in S$ の場合だけ受理する。従って、この多項式サイズ回路族は $L_S$ を決定し、 $L_S\in\mathsf{P/poly}$ である。

Turing 機械の有限記述は可算個しかない一方、 $\mathbb N$ の部分集合は非可算個ある。従って、どの Turing 機械にも決定されない集合 $S\subseteq\mathbb N$ が存在する。 $L_S$ の決定器が存在すれば、入力 $n$ から $1^n$ を作ってその決定器を実行することにより、 $n\in S$ を決定することができる。従って、この $L_S$ は決定不能であるが、上の線形サイズ回路族をもつ。▨

この命題は、P/poly の個々の回路 $C_n$ を効率的に評価することと、回路族全体を効率的に生成することが別の条件であることを示す。特定の自然な問題に対する回路下界を与えるものではない。

5 回路下界の量化

言語 $L$ に対し、長さ $n$ における特性関数

f_{L,n}(x)= \begin{cases} 1 & (x\in L),\\ 0 & (x\notin L) \end{cases} \qquad (x\in\{0,1\}^n)

を計算する最小の Boolean 回路サイズを $s_L(n)$ と書く。Boolean 関数は真理値表から積和標準形の回路を作ることができるため、この最小値は全ての $n$ で存在する。

命題 5.1. 言語 $L$ が $\mathsf{P/poly}$ に属さないことと、任意の整数 $k\ge0$ と任意の実数 $c>0$ に対して

s_L(n)>c(n+1)^k

となる $n$ が無限個存在することは同値である。

証明. $L\in\mathsf{P/poly}$ なら、ある $c>0$ と整数 $k\ge0$ が存在して、全ての $n$ で $s_L(n)\le c(n+1)^k$ となる。従って、表示した無限性条件は成り立たない。

逆に、表示した無限性条件が成り立たないとする。このとき、ある $c>0$ と整数 $k\ge0$ について、 $s_L(n)>c(n+1)^k$ となる $n$ は有限個しかない。その有限集合を $E$ とし、

c'=\max\left( c, \max_{n\in E}\frac{s_L(n)}{(n+1)^k} \right)

と置く。 $E$ が空なら二つ目の最大値を省く。すると全ての $n$ で $s_L(n)\le c'(n+1)^k$ である。各 $n$ で最小回路を一つ選べば、 $L$ を決定する多項式サイズ回路族を得るため、 $L\in\mathsf{P/poly}$ である。対偶により結論を得る。▨

注意 5.2 (下界で固定すべき対象). 入力長 $n$ ごとに「サイズの大きい Boolean 関数が存在する」と示す量化は

\forall n\ \exists f_n

である。この量化だけでは、あらかじめ固定した一つの言語 $L$ の特性関数列 $(f_{L,n})_{n\ge0}$ に対する下界にならない。さらに、一様な回路族だけを排除する下界と、全ての非一様な回路族を排除して $L\notin\mathsf{P/poly}$ を示す下界も異なる。ゲート集合、fan-in、サイズまたは深さ、一様性、および「全ての入力長」か「無限個の入力長」かを固定してから、下界の主張を記述する必要がある。

本記事は回路下界を証明するための量化を整理するところまでを扱う。定数深さ回路などに対する具体的な下界、有限構造上の論理による計算量の特徴付け、および量子回路は、それぞれ別の計算モデルを必要とするため扱わない。

6 演習

問題 6.1.

入力 $x$ ごとに、その $x$ だけに正しい回路 $C_x$ を多項式時間で生成するという条件が、P 一様性の定義と異なる理由を説明せよ。
定理 3.1の前向きの構成で、一つの局所更新に必要なゲート数が入力長によらない理由を説明せよ。
P/poly の定義から一様性を除くと、決定不能な単項言語を含み得る理由を説明せよ。
各 $n$ について大きい回路を必要とする関数が一つ存在するという主張だけでは、固定した言語の P/poly 下界にならない理由を、量化の順序を用いて説明せよ。

解答 (演習の要点).

P 一様性の生成器は $x$ を受け取らず、 $1^n$ だけから長さ $n$ の全入力に共通する回路を出力する。 $C_x$ を許す条件では、同じ長さの異なる入力に同一の回路を用いるという回路族の要件が失われる。
局所関数の入力集合は $A^3$ であり、機械の状態集合とテープアルファベットを固定すると $A$ の大きさも固定される。従って、その真理値表を実装する部分回路のサイズは定数である。
各入力長の答えを定数回路へ一ビットずつ埋め込み、回路列を生成するアルゴリズムを要求しないためである。
前者では入力長ごとに別の関数 $f_n$ を後から選ぶことができる。固定した言語の下界では、最初に一つの $L$ を固定し、その特性関数列が任意の多項式上界を無限個の入力長で超えることを示す必要がある。

▨

§E15.16回路計算量