第 x 回回路計算

本日の内容

1. 回路計算
2. アドバイス関数によるクラスと回路計算量
3. 並列計算
4. 参考文献

今回は回路や並列計算の計算量について説明します。

1. 回路計算

入出力のある装置で問題の答を得ることを考えます。この時、問題の複雑度を考えるにはどのようにすればよいでしょうか?

特定の基本的な素子を考え、それだけでその問題を解くことを考え、その素子数などで問題の複雑度を考えます。

論理演算の集合 $B$ に対して、 $B$ が関数的完全とは、 $B$ に含まれる演算の組み合わせだけですべての関数が実現できることを言います。

論理回路

2入力の and, or演算と not 演算は基底となり、これで作られた回路であらゆる論理関数が実現できます。さらに、実回路としても容易に構成できます。これらで作られた回路を論理回路(Boolean circuit) と呼びます。演算素子をゲートと呼びます。なお、2入力の代わりに多入力で考えることもあります。また出力も1つだけでなく、多出力も考えることがあります。このような入出力の条件を示すのに、 fan-in, fan-out という用語を使用することがあります。

さて、論理回路は、1,2入力1出力という制限のあるループのない有向グラフとなります。ゲートnot, and, or はグラフのノードのラベルとし、接続を辺で表します。この時、単純に、各ゲートのラベル、入力ノード名、出力ノード名という組を考えます。また、入力ゲートを $x_{1}, ..., x_{n}$ で表し、出力ゲートを $y_{1}, ..., y_{n}$ で表します。

$(not, 0, 1)$
$(and, 2, 3, 4)$
$(or, 5, 6, 7)$

このようにすると、論理回路をこの表現で文字列で表すことができます。ゲート数を $N$ とすると、ゲートを表現するのに $log N$ ビット程度の文字数が必要となり、また、各ゲートの表現は定数個のゲートの表現の組程度になるので、論理回路の表現の長さは $N log N$ 程度の文字列で表現できます。

論理関数 $f$ に対して、 $c (f)$ 計算する最小の論理回路Cのゲートの素子数とする。また、 $d (f)$ をfを計算する深さ最小の論理回路 C の入力ゲートから出力ゲートまでの最長パス長とする。

集合 $A \subseteq N$ に対して、長さ $n$ の回路複雑度 $c_{A} (n)$ は、長さ $n$ だけの $A \cap {0, 1}^{n}$ 特性関数の回路複雑度として定義する。長さ $n$ の深さ複雑度 $d_{A} (n)$ も同様に定義する。

補題

2つの長さ $n$ の論理ベクトル $x = (x_{1}, ..., x_{n})$ と $y = (y_{1}, ..., y_{n})$ の内積 $dot (x, y) = ⋁_{i = 1}^{n} x_{i} \land y_{i}$ の回路複雑度は $d (dot) \geq log n + 1$ , $c (dot) = O (n^{2})$

補題

2つの $n \times n$ 正方論理行列 $A, B$ の積について、 $d (A B) \geq log n + 1$

(証明) 各積の要素 $c_{i, j} = dot (a_{i}, b_{j})$ は独立に計算できる □

補題

$n \times n$ の正方論理行列 $A$ の $A^{*} = ⋁_{k = 0}^{∞} A^{k}$ に対して、 $d (A^{*}) = O ({log}^{2} n)$

（証明） $A^{0} = I$ を単位行列とする。

$a_{i j}^{0} = 1$ $(i = j)$
$a_{i j} = 1$ の時、 $a_{i j}^{1} = 1$
$a_{i j}^{2} = ⋁_{k = 1}^{n} a_{i, k} \land a_{k, j}$ これが成立するには、ある $k_{1}$ が存在して、 $a_{i k_{1}} = a_{k_{1} j} = 1$
$a_{i j}^{3} = ⋁_{k = 1}^{n} a_{i, k}^{2} \land a_{k, j}$ より、ある $k_{2}$ が存在して、 $a_{i, k_{1}}^{2} = a_{k_{2} j} = 1$ より、ある、 $k_{1}, k_{2}$ が存在して、 $a_{i, k_{1}} = a_{k_{1}, k_{2}} = a_{k_{2}, i} = 1$ となる。
したがって、 $a_{i, j}^{*}$ が1になるには、 $i = j$ か、 $a_{i, k_{1}}$ , $a_{k_{1}, k_{2}}$ , $a_{k_{2}, k_{3}}$ ,..., $a_{k_{l}, j}$ のそれぞれが1になっている必要がある。なお、この $a_{i, k_{1}}$ , $a_{k_{1}, k_{2}}$ , $a_{k_{2}, k_{3}}$ ,..., $a_{k_{p}, k_{p + 1}}$ ,..., $a_{k_{q}, k_{q + 1}}$ ,..., $a_{k_{l}, j}$ で、 $k_{p} = k_{q}$ の時、 $a_{i, k_{1}}$ , $a_{k_{1}, k_{2}}$ , $a_{k_{2}, k_{3}}$ ,..., $a_{k_{p}, k_{q + 1}}$ ,..., $a_{k_{l}, j}$ としても $i$ から $j$ まで1の列が得られる。したがって、これより、 $k_{1}$ , ... , $k_{l}$ はすべて異なると仮定できる。そのため、この列は最長でも $n$ になる。つまり、 $A^{*} = {(I \lor A)}^{n}$ と置き換えられる。

これはすべて同じ回路の論理積なので、 $O (log n)$ 段で ${(I \lor A)}^{n}$ を計算できる。 □

定理

$A$ が1テープ決定性チューリングマシンで $T (n)$ 時間内に受理できれば、 $c_{A} (n) = O ({T (n)}^{2})$

（証明） Cook の定理同様、様相を論理変数で表し、遷移のルールも論理式で表す。決定性チューリング機械なので、途中の様相から次の様相の値は論理式を計算すれば求められる。様相のサイズは $O (T (n))$ , また次の様相を計算する際、処理する情報は有限個の論理変数のみなので（状態は有限個、読み、変更し、書き出すテープのマス目も有限個）、一つの様相から次の様相を計算する論理回路のゲート数は $O (T (n))$ で深さは定数段になる。したがって、 $T (n)$ 時間のシミュレーションは $O ({T (n)}^{2})$ サイズの回路で作ることができる。また、深さは $O (T (n))$ である。 □

定理

入力テープが読み込みのみ可能で、作業用テープが入力の長さ $n$ に対して、 $S (n)$ ( $S (n) \geq log n$ ) だけ使用できるような決定性チューリングマシンで、 $A$ が受理できるとする。その時、 $d_{A} (n) = O ({S (n)}^{2})$

（証明）一般性を失わず、受理するときに作業用テープをすべて0で消し、入力テープヘッドも作業用テープヘッドも左端に移動してから受理状態に入ることとする。これにより、受理様相は一つだけに限定できる。

さて、様相として、状態と作業用のテープの内容のほか、入力テープの読み込みヘッドの位置を考える。入力テープの読み込みヘッド位置を二進数で表現すると、 $O (log n)$ で表現できる。そのため、様相の長さは $O (log n + S (n))$ となる。この長さで表せる様相すべて考えると $2^{log n + S (n)}$ 通りとなる。決定性の計算なので、計算が止まる条件は、計算の過程でこのすべての様相が高々1回だけしか出現しないことである。

ここで、入力テープの内容は変化せず、様相とは別に設定できるため、入力テープの内容が $x$ の時、様相 $a$ が様相 $b$ に 1 stepで遷移できるという論理関数 ${step}_{a, b} (x)$ を考えることができる。実は、この計算は、入力テープのヘッド位置が $k$ の入力 $x_{k}$ の値だけで決定されるので、深さは 1 で実現できる。

次に、2 stepで遷移可能かどうかを判定する場合、中間様相 $c$ を考えると、ある $c$ があって、 ${step}_{a, c} (x) \land {step}_{c, b} (x)$ となればいいので、 $\underset{c}{⋁} {step}_{a, c} (x) \land {step}_{c, b} (x)$ となる。結局これも様相による正方行列における閉方を考えればいいので、様相の数に対して $O ({(log 2^{S (n)})}^{2}) = O ({S (n)}^{2})$ の深さの回路で実現できる。 □

2. アドバイス関数によるクラスと回路計算量

クラス $C$ と、アドバイス関数族 $F$ により、 $C / F$ を定義する。 $B$ が $C / F$ に含まれるとは、 $C$ に含まれる集合 $A$ と $F$ に含まれる関数 $f$ について、 $B = {x | (x, f (| x |)) \in A}$

$C / F$ は nonuniform なクラスとして知られている。 $C / F$ として $P / poly$ などが研究されている。

CVP(circuit value problem) は入力として $(x, c)$ で回路表現 $c$ に対して $c (x)$ の論理値を求める問題とする。

定理

$CVP \in P$

定理

$A$ が polynomial サイズの回路を持つ $\leftrightarrow A \in P / poly$

これにより、回路での現実的に構成可能なクラスは $P / poly$ という風に捉えることができます。

(証明) (→) $A$ を認識する polynomial サイズの回路列 $C_{n}$ を考える。アドバイス関数として $h (n) = C_{n}$ とすると、 $(x, h (| x |))$ がtrue かどうかを判断するのは $CVP$ なので、 $P$ に含まれる。したがって、 $A \in P/poly$

(←) $A$ が $P / poly$ に含まれているとすると、アドバイス関数 $h$ と $P$ に含まれている集合 $B$ に対して、 $x \in A \leftrightarrow ⟨ x, h (| x |) ⟨ \in B$ となる。 $B$ は $P$ に含まれるので、決定性多項式時間の1テープチューリング機械 $M$ が存在する。決定性多項式時間のチューリング機械は実行時間の2乗サイズの回路で計算できる。 $n$ を固定した場合、 $h (| x |) = h (n)$ も定数となり、また、 $⟨ x, h (| x |) ⟨$ と組を作るのも多項式時間でできるため、 $n$ を固定した $(x, h (| n |))$ が $B$ に含まれるか判定する回路も多項式サイズで構成できる。 □

定理

EXPTIME にP/poly に含まれない問題が存在する。

（証明）指数時間を使って対角化します。

定理

BPP∈P/Poly［Adleman 1978］

(証明) $A$ が $BPP$ に含まれるとする。すると、長さ $n$ の入力に対して、必要な乱数の長さはある多項式 $r (n)$ であるとし、2入力の多項式時間決定性チューリングマシンで以下を仮定している。を仮定する ( 誤り率を $\frac{1}{2^{n + 1}}$ 以下としている)。

$x \in A \to \underset{r \in {0, 1}^{r (| x |)}}{Pr} [M (x, r) = 1] > 1 - \frac{1}{2^{| x | + 1}}$
$x \notin A \to \underset{r \in {0, 1}^{r (| x |)}}{Pr} [M (x, r) = 0] > 1 - \frac{1}{2^{| x | + 1}}$

各長さ $n$ の入力 $x$ についてそれぞれ、正解を出す乱数列が $2^{r (n)} (1 - \frac{1}{2^{n + 1}})$ 以上の個数がある。すると、全入力 $x$ について、少なくとも１つの入力に対して誤りを出す乱数列は $2^{n} 2^{r (n)} \frac{1}{2^{n + 1}} = 2^{r (n)} / 2$ 以下となる。つまり、残りの $2^{r (n)} / 2$ 以上の乱数はすべての入力で正解を出す。長さ $n$ のすべての入力に対して、正解を出す乱数列 $r$ をアドバイス関数の値として入力に付与すれば、 $M (x, r)$ は決定性チューリングマシンで多項式時間で常に正解を出すため、これは、 P/poly の定義を満たす。 □

3. 並列計算

NC (Nick's Class) は Nick Pippenger が特徴づけをした計算量のクラスで、多項式個のプロセッサが対数多項式の深さで計算できるクラスです。但し、構成については uniformity(一様性)が仮定されています。

Uniformity とは、回路の構成を、入力の長さに対して、多項式時間やlog領域の制限を設けることを言います。この制限があるため、P/poly と NC は異なり、 $NC \subseteq P$ が成り立ちます。 NCに関する未解決問題はNC=P?か否かになります。 NC=Pならば、多項式時間計算可能なものはすべてlog多項式時間の並列計算が可能ということになります。しかし、現状ではP完全問題に関して、NCに含まれないと信じられています。ここでP完全問題とはPに含まれる任意の問題が log 領域 many-one reducibleな問題

${NC}^{1} \subseteq L \subseteq NL \subseteq {NC}^{2}$

4. 参考文献

José Luis Balcázar, Josep Díaz, Joaquim Gabarró "Structural Complexity I" Springer Berlin Heidelberg; 2nd ed. 1995.
河村「ランダム性と計算量」 https://www.kurims.kyoto-u.ac.jp/~kawamura/t/kyushu/R051124.pdf 令和5年11月24日

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 x 回 回路計算