今回は回路や並列計算の計算量について説明します。
入出力のある装置で問題の答を得ることを考えます。 この時、問題の複雑度を考えるにはどのようにすればよいでしょうか?
特定の基本的な素子を考え、それだけでその問題を解くことを考え、その素 子数などで問題の複雑度を考えます。
論理演算の集合 に対して、 が関数的完全とは、 に含まれる演算の組み合わ せだけですべての関数が実現できることを言います。
2入力の and, or演算と not 演算は基底となり、これで作られた回路であら ゆる論理関数が実現できます。 さらに、実回路としても容易に構成できます。 これらで作られた回路を論理回路(Boolean circuit) と呼びます。 演算素子をゲートと呼びます。 なお、2入力の代わりに多入力で考えることもあります。 また出力も1つだけでなく、多出力も考えることがあります。このような入 出力の条件を示すのに、 fan-in, fan-out という用語を使用することがあ ります。
さて、論理回路は、1,2入力1出力という制限のあるループのない有向グラフと なります。 ゲートnot, and, or はグラフのノードのラベルとし、接続を辺で表します。 この時、単純に、各ゲートのラベル、入力ノード名、出力ノード名という組 を考えます。 また、入力ゲートを で表し、出力ゲートを で表し ます。
このようにすると、論理回路をこの表現で文字列で表すことができます。 ゲート数を とすると、ゲートを表現するのに ビット程度の文字数 が必要となり、また、各ゲートの表現は定数個のゲートの表現の組程度になる ので、 論理回路の表現の長さは 程度の文字列で表現できます。
論理関数に対して、 計算する最小の論理回路Cのゲートの素子数とする。 また、 をfを計算する深さ最小の論理回路 C の入力ゲートから出力ゲートまで の最長パス長とする。
集合 に対して、長さ の回路複雑度 は、 長さ だけの 特性関数の回路複雑度として定義する。 長さ の深さ複雑度 も同様に定義する。
2つの長さ の論理ベクトル と の内積 の回路複雑度は ,
2つの 正方論理行列 の積について、
(証明) 各積の要素 は独立に計算できる □
の正方論理行列 の に対して、
(証明) を単位行列とする。
これはすべて同じ回路の論理積なので、 段で を計算できる。 □
が1テープ決定性チューリングマシンで 時間内に受理できれば、
(証明) Cook の定理同様、様相を論理変数で表し、遷移のルールも論理式で表す。 決定性チューリング機械なので、途中の様相から次の様相の値は論理式を計 算すれば求められる。 様相のサイズは , また次の様相を計算する際、処理する情報は有限 個の論理変数のみなので(状態は有限個、読み、変更し、書き出すテープの マス目も有限個)、一つの様相から次の様相を計算する論理回路のゲート数 は で深さは定数段になる。 したがって、 時間のシミュレーションは サイズの回路で 作ることができる。 また、深さは である。 □
入力テープが読み込みのみ可能で、作業用テープが 入力の長さ に対して、 ( ) だけ使用できるような 決定性チューリングマシンで、 が受理できるとする。 その時、
(証明)一般性を失わず、受理するときに作業用テープをすべて0で消し、入力テープ ヘッドも作業用テープヘッドも左端に移動してから受理状態に入ることとする。 これにより、受理様相は一つだけに限定できる。
さて、 様相として、状態と作業用のテープの内容のほか、入力テープの読み込みヘッ ドの位置を考える。 入力テープの読み込みヘッド位置を二進数で表現すると、 で表現 できる。 そのため、様相の長さは となる。 この長さで表せる様相すべて考えると 通りとなる。 決定性の計算なので、計算が止まる条件は、計算の過程でこのすべての様相 が高々1回だけしか出現しないことである。
ここで、入力テープの内容は変化せず、様相とは別に設定できるため、 入力テープの内容が の時、様相 が様相 に 1 stepで遷移できるという論理 関数 を考えることができる。 実は、この計算は、入力テープのヘッド位置が の入力 の値だけで決定さ れるので、深さは 1 で実現できる。
次に、2 stepで遷移可能かどうかを判定する場合、中間様相 を考えると、 ある があって、 となればいいので、 となる。 結局これも様相による正方行列における閉方を考えればいいので、 様相の数に対して の深さの回路で実現できる。 □
クラス と、アドバイス関数族 により、 を定義する。 が に含まれるとは、 に含まれる集合 と に含まれる関数 に ついて、
は nonuniform なクラスとして知られている。 として などが研究されている。
CVP(circuit value problem) は 入力として で回路表現 に対して の論理値を求める問題とする。
が polynomial サイズの回路を持つ
これにより、回路での現実的に構成可能なクラスは という風に捉え ることができます。
(証明) (→) を認識する polynomial サイズの回路列 を考える。 アドバイス関数として とすると、 がtrue かどうかを判断するのは なので、 に含まれる。 したがって、
(←) が に含まれているとすると、アドバイス関数 と に含まれている 集合 に対して、 となる。 は に含まれるので、決定性多項式時間の1テープチューリング機械 が存在 する。 決定性多項式時間のチューリング機械は実行時間の2乗サイズの回路で計算 できる。 を固定した場合、 も定数となり、また、 と組を作るのも多項式時間でできるため、 を固定した が に含まれるか判定する回路も多項式サイズで構 成できる。 □
EXPTIME にP/poly に含まれない問題が存在する。
(証明) 指数時間を使って対角化します。
BPP∈P/Poly[Adleman 1978]
(証明) が に含まれるとする。 すると、長さ の入力に対して、必要な乱数の長さはある多項式 で あるとし、2入力の多項式時間決定性チューリングマシンで以下を仮定して いる。 を仮定する ( 誤り率を 以下としている)。
各長さ の入力 についてそれぞれ、正解を出す乱数列が 以上の個数がある。 すると、全入力 について、少なくとも1つの入力に対して誤りを出す乱 数列は 以下となる。 つまり、残りの 以上の乱数はすべての入力で正解を出す。 長さ のすべての入力に対して、正解を出す乱数列 をアドバイス関数の 値として入力に付与すれば、 は決定性チューリングマシンで多項式時間で常に正解を出すため、 これは、 P/poly の定義を満たす。 □
NC (Nick's Class) は Nick Pippenger が特徴づけをした計算量のクラスで、 多項式個のプロセッサが対数多項式の深さで計算できるクラスです。 但し、構成については uniformity(一様性)が仮定されています。
Uniformity とは、回路の構成を、入力の長さに対して、多項式時間やlog領 域の制限を設けることを言います。 この制限があるため、P/poly と NC は異なり、 が成り立ちます。 NCに関する未解決問題はNC=P?か否かになります。 NC=Pならば、多項式時間計算可能なものはすべてlog多項式時間の並列計算 が可能ということになります。 しかし、現状ではP完全問題に関して、NCに含まれないと信じら れています。 ここでP完全問題とはPに含まれる任意の問題が log 領域 many-one reducibleな問題