・$E\not\subseteq \mathrm{SIZE}[2^{\Omega(n)}]$ (脱乱択化におけるPRG構成の文脈)
・$NP \not \subseteq \mathrm{coNP/poly}$ (FPTのカーネル化の文脈)
・$NEXP \not \subseteq \mathrm{P}/\mathrm{poly}$ (PITの脱乱択化の文脈)
といったものがあります。既存結果の下界はどのような仮定の下で成り立つのかを把握する際にもこれらはどのようなクラスなのかを知っておく必要があります。「/poly」という概念は問題がuniform/nonuniformに解けるということを表します。ここではuniform/nonuniformに解けるとはどういうことかを説明します。
計算量理論には回路計算量というトピックがあります。これはある判定問題に対してそれを解く回路のうち最小サイズがどの程度になるかということを考えます。P$\neq$NP予想は「NP問題のうち多項式時間で解けないものが存在する」ことを意味しますが、同様に NP$\neq$P/poly という予想があります。これは「NP問題のうち多項式サイズの回路で解けないものが存在する」ことを意味します。
それでは、「多項式時間で解ける」ことと「多項式サイズの回路で解ける」ことは異なるのでしょうか？
回路とはどのようなものかを思い出すと、and/or/notゲートとinputゲートからなるDAGであって、$n$変数の回路$C_n$が関数$f:\{0,1\}^n\to\{0,1\}$を計算するというのは
$\forall x\in\{0,1\}^n:C_n(x)=f(x)$
$\forall n\in \mathbb{N}$, $C_n$が$L_n$を解く ($L_n$は$L$の入力長$n$への制限)
結論からいうと問題$L$に対してそれが
・uniformに解ける ＝ $L$を解くあるチューリング機械$M$が存在する
・nonuniformに解ける = $L$を解くある回路族$\{C_n\}_n$が存在する
ことをいいます。言い換えると、uniformに解けるといった場合は一つの機械があれば全ての入力に対応できることを意味しており、nonuniformに解けるといった場合は入力長$n$毎に異なる回路を用意できれば解けることを意味します。P/polyは多項式サイズの回路で解ける問題クラスです。
任意のアルゴリズムは少ないオーバーヘッドで回路に変換できる（c.f. Cook-Levinの定理: 3SATのNP困難性の証明) ので、uniformに解けるならばnonuniformで解けます。一方でnonuniformで解けるからといってuniformでも解けるとは限りません。
例えば以下の問題を考えます：
停止性判定問題
入力: $x\in\{0,1\}^*$
出力: Yes iff $x=1^n$ かつ 「$n$を二進表記した文字列が表すチューリング機械が任意の入力に対し有限時間で停止する」
この問題は入力が特別なフォーマットにしたものと捉えることができますが本質的には停止性判定問題を解かなきゃいけないのでuniformには解けません。一方でnonuniformに解くことはできます。回路$\{C_n\}_n$を各$n$ に対し、$x=1^n$ かつ「$n$を二進表記した文字列が表すチューリング機械が任意の入力に対し有限時間で停止する」ような $n$ ならば $C_n(x)=x_1\land x_2\land \cdots \land x_n$ とし, そうでないならば恒等的に0 (例えば $C_n(x)=x_1\land \overline {x_1}$) とすれば、実際に正しい答えを出力しています。
少しいじわるな例だったかもしれませんが、nonuniformに解けるといったときには $n$毎に回路 $C_n$ は外から用意されているから $n$ に問題の本質的な情報を埋め込まれたようなフォーマットの問題に対してはnonuniform と uniform の間にギャップが誕生してしまいます。
一方で、nonuniformに解けるかつ解く回路が構成できるならばuniformに解けます。
0 件のコメント:
コメントを投稿