判定問題を解くアルゴリズムを実行しているチューリング機械は回路によって表現できます. 実行時間 $T$ のアルゴリズムはサイズ $O(T\log T)$ の回路によって模倣することが出来ます. 具体的にはチューリング機械の「1ステップ模倣回路」を構築し, これを $T$ 段積み重ねれば所望の回路が得られます. いわば, 回路は計算を模倣するモデルであるため, その研究は計算の本質を掴む良いアプローチになるというわけです.
さて, 多項式時間アルゴリズムの動作は多項式サイズの回路によって模倣できる (専門用語で言うとP $\subseteq $ P/poly が成り立つ) ので, 対偶をとると「多項式サイズ回路で解けない問題は多項式アルゴリズムで解けない」ことが言えます.
多項式時間アルゴリズムで解ける判定問題のクラスはPと呼ばれますが, 多項式サイズの回路で解ける判定問題のクラスは P/poly と呼ばれます. もう少しちゃんと言うと, 判定問題とは言語 $L \subseteq \{0,1\}^*$ のことであり, インスタンス $x\in\{0,1\}^*$ に対して $x\in L$ か否かが問われます. 言語 $L$ は以下の条件を満たすとき, P/poly に属すると言います:
(条件) ある回路族 $\{C_n\}_{n\in\mathbb{N}}$ が存在して, 各$n$に対して$C_n$の素子数は$n$の多項式で上から抑えられており, さらに任意の$x\in\{0,1\}^*$ に対して $C_{|x|}(x)=1$ iff $x\in L$ が成り立つ. ここで $|x|$ は$x$の文字数.
冒頭に述べたように, (チューリング機械上の)多項式時間アルゴリズムは多項式サイズの回路によって模倣できるため, PはP/poly に含まれます. この包含関係はstrictで, 以下に示すように, 実はP/polyは計算不可能な判定問題も含んでいます:
例: ビット列 $x\in \{0,1\}^n$ とチューリング機械が一対一対応することが知られています (チューリング機械全体は加算無限個). そこで, 自然数$n$に対してその二進表記に対応するチューリング機械を$M_n$と表すことにします. さて, 言語 $L$ として $L=\{1^n: M_n$ は任意の入力に対して停止する $\}$ と定めます. このとき $L\in $P/polyが成り立ちます. 実際, $C_n$として, $x=1^n$かつ$M_n$が停止するならば $C_n(x)=1$, そうでないならば $0$ を出力する回路とすると, $C_n$のサイズは $O(n)$ です ($M_n$が停止するかどうかは神様が知っていて, その神様が各$n$に対して$C_n$を設計してくれた, と思ってください. クラスP/polyでは, 回路族の存在性を要請しているのであってその回路族がチューリング機械によって構成できかどうかは要請していません！). すると $C_n$ は $L$を解くので, $L\in $P/polyとなります.
回路計算量理論では, 色んな問題に対してその問題を解く回路のサイズはどれくらいなのかを研究しています. 具体的には問題クラスの回路下界や, 回路のタイプを制限 (単調回路など) したときの回路下界などが研究されています.
前置きが長くなりましたが, 本記事では脱乱択化と回路計算量下界の関係について概説します.
ZEROPの脱乱択化
与えられた多変数多項式 $P(x_1,\ldots,x_n)$ が恒等的に $0$ かどうかを判定する問題をZEROP と呼びます. ここで入力は以下の例のように算術回路で与えられるものとします.
この問題はランダムな値を代入したときに$0$になるかどうかを確認し, これを繰り返すことにより, with high probability で解くことができます (例えばこの記事で紹介されているSchwartz-Zippelの補題を参照してください). 実は, ZEROPはクラスPに属するか否かは未解決です (計算量理論ではpseudorandom generatorが存在し即ちP=BPPであると信じられているため, ZEROPはクラスPに属するだろうと信じられています).
Schwartz-Zippelの補題が脱乱択化できればZEROPも脱乱択化できてハッピーなのですが, ZEROPの脱乱択化に関して以下の結果が知られています:
定理1 [Kabanets Impagliazzo, 2003]
以下の三つの主張のうち, 少なくとも一つは偽である.
(1). ZEROPはクラスPに属する.
(2). 01行列のパーマネントは多項式サイズの算術回路で解ける.
(3). NEXP $\subseteq$ P/poly.
それぞれの主張を見ていきます. (1)は上記の通りで, ZEROPが脱乱択化出来るということを意味します. (2)は読んだままです. 多項式サイズの算術回路で解けるというのはP/polyの算術回路版のような意味です. 普通の回路では各ゲートに and か or が記されていますが算術回路では + , -, × のいずれかが記されており, 出力ゲートからは期待した値が出てくるようなものです (そのため, 計算途中のビット長などは気にしません). (3)のNEXPというのはNPの指数時間verです. NPは非決定的チューリング機械で多項式時間で解ける問題のクラスですが, NEXPは非決定的チューリング機械で指数時間 (i.e., $2^{\mathrm{poly}(n)}$時間) で解ける問題のクラスです. なので, P$\subseteq$NPと同様にEXP$\subseteq$NEXPが成り立ちますが, EXP$\neq$NEXPかどうかは未解決です (P$\neq$NPならばEXP$\neq$NEXPが直ちに従います).
つまり, 定理1より, ZEROPが脱乱択化できたら, either パーマネントは多項式サイズの算術回路で計算できない or NEXPというクラスは多項式サイズの回路で解けないことが分かるため, 回路計算量の下界が得られたことになります. これが脱乱択化によって示される回路計算量下界ということになります.
定理1の証明を全て網羅しようとすると, pseudorandom generator, 対話証明 (クラスMAとか), IP=PSPACE, 戸田の定理, 非決定性の時間階層定理, easy witness lemmaといった多くの前提知識が必要となりとても大変です. なので本記事では計算量クラスには出来るだけ触れず, なぜパーマネントやZEROPが登場するかについて重きをおいた議論について概説したいと思います.
以下の補題を考えます. 専門用語が多いので, 下に概説を付け加えました.
補題1.
NEXP $\subseteq$ P/poly ならば, NEXP=EXP.
補題2 (非決定性チューリング機械の時間階層定理).
NEXP ≠ NP.
補題3 (Meyerの定理).
$\Sigma_2$を, $\exists x\forall y: \phi(x,y)$ の判定問題として表せる問題のクラスとする ($\phi$は論理式). このとき, $\mathrm{EXP}\subseteq \mathrm{P}/\mathrm{poly}$ ならば $\mathrm{EXP}=\Sigma_2$.
補題4 (戸田の定理の特殊ケース).
$\Sigma_2\subseteq \mathrm{P}^{\mathrm{perm}}$.
補題1は, easy witness lemma (IKW02) と呼ばれる面白い結果から従うのですが, その証明をしようとするとpseudorandom generator, クラスMAなどの説明から始めなくてはならずとても大変なので本記事ではそこまでしません. 補題2は時間階層定理の非決定性verです. 証明は決定性の時と同じようにはいかず, 少し難しいです. 補題3における$\Sigma_2$とは多項式時間階層の一つです. 例えばNPの問題は多項式長の証拠が存在するような問題なので, $\exists x:\phi(x)$ という形で書けるのですが, ここに出てくる量化子を交互に繰り返した問題を考えることで多項式時間階層 (PH: polynomial hierarchy) が構成されます. もう少しちゃんと言うと, 量化子が有限回交互に繰り返された形で書ける問題のクラスをPHと呼びます. ちなみに, coNPという計算量クラスは $\forall x: \phi(x)$ の形で書けるものであり, $\exists$と$\forall$を入れ替えたものとして解釈できるため, coNP$\subseteq$ PHです. $\mathrm{P}^{\mathrm{perm}}$とは, 行列のパーマネントを計算するオラクルを用いて多項式時間で判定できる問題のクラスです (厳密には, 行列$A$とインデックス$i$を受け取り, $A$のパーマネントの第iビット目が0か1かを判定するというオラクルを持ったチューリング機械で多項式時間で判定出来る問題のクラスです). 戸田の定理は PH$\subseteq \mathrm{P}^{\mathrm{perm}}$ を主張しており, 戸田 誠之助先生によって1981年に発表されました. この定理は計算量理論において非常に重要な定理として知られています. とても面白い解説がこちらにあるので, 興味のある方はぜひ目を通してみてください. 上に述べた補題はどれも重要な結果なので補題というよりそれ自体が定理になるような結果です. 本記事では補題1~4を認めて定理1の証明を行います.
定理1の証明.
主張(1)~(3)が成り立つと仮定するとNEXP=NPになってしまい補題2に反する, という流れで証明します. まず
主張(1),(2)⇒$\mathrm{P}^{\mathrm{perm}}\subseteq \mathrm{NP}$
を示します. まず, $\mathrm{P}^{\mathrm{perm}}$ に属する問題Xに対して多項式長の証拠があることを言います. この問題Xはパーマネントをオラクルとした多項式時間アルゴリズムで解くことが出来るので, オラクル呼び出しの部分をパーマネントを計算する多項式サイズの回路に置き換えることができます (c.f. 主張(2)). より正確には, 主張(2)より行列のパーマネント計算は多項式サイズの回路の族$\{C_n\}$で解くことが出来るため, この回路を表現するビット文字列をwitnessとして与え, そのwitnessで得られた回路をオラクル呼び出しの部分に置き換えることで問題Xを解きます. このとき, NPに属することをちゃんと証明するためには, この記事にあるように, witnessで与えられた回路が本当にパーマネントを計算しているかどうかをチェックする必要があります. このチェックする部分で主張(1)を用います.
今, 算術回路族$\{C_i\}$を持っていて ($i\leq \mathrm{poly}(n)$), 各$C_i$が本当にサイズ$i\times i$の行列のパーマネントを計算するかどうかをチェックしたいとしましょう. 明らかに$1\times 1$行列のパーマネント計算の回路のチェックは簡単です. さて, $C_1,\ldots,C_t$がそれぞれ正しいとしたとき, $C_{t+1}$の正当性のチェックを行うアルゴリズムを考えます. $A$を$(t+1)\times (t+1)$行列として, その$1$行目と$j$列目だけを除去して得られる$t\times t$行列を$A_{1,j}$とします (下図参照).
$\mathrm{perm}(M)$ で行列 $M$ のパーマネントを表すとします. すると, 行列式の展開と同じ要領で, $\mathrm{perm}(A)=\sum_{j=1}^{t+1} \mathrm{perm}(A_{1,j})$ が成り立つことが分かります. 今, 行列$A$を引数として持つ多項式
$P(A):=\sum_{j=1}^{t+1}C_t(A_{1,j})-C_{t+1}(A)$ ..........(＊)
を考えます. 各回路$C_t,C_{t+1}$は算術回路として表現されているので多項式になっていることに注意してください. 帰納法の仮定より, $C_t(A_{1,j})=\mathrm{perm}(A_{1,j})$なので, $C_{t+1}$がパーマネントを正しく計算する iff $P(A)$は恒等的に$0$. したがって$(t+1)^2$変数多項式 $P$ に対して ZEROP を解くことによって, witnessとして与えられた回路族 $\{C_t\}$ が正しくパーマネントを計算するかどうかをチェックすることが出来るので, $\mathrm{P}^{\mathrm{perm}} \subseteq \mathrm{NP}$ が成り立ちます.
EXP$\subseteq$NEXPなので, 主張(3)より, EXP$\subseteq$P/polyです. したがって
主張(3)⇒$\mathrm{NEXP}=\mathrm{EXP}$.
主張(3) & 補題3 ⇒$\mathrm{EXP}\subseteq \Sigma_2$.
補題4 & 主張(＊)⇒$\Sigma_2 \subseteq \mathrm{P}^{\mathrm{perm}} \subseteq \mathrm{NP}$.
これらを組み合わせると, 主張(1)~(3) ⇒ $\mathrm{NEXP}\subseteq \mathrm{NP}$ となり, 補題2と矛盾が生じます. よって主張(1)~(3)が全て真になることはありません.
参考文献
S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press.
0 件のコメント:
コメントを投稿