NEXP探索問題 - 某理論計算機科学者の研究日誌

NP問題は良く知られているように降下型自己帰着(downward self-reduction)を持ちます．つまり，長さ $n-1$ 以下のインスタンスの判定を行うオラクルがあれば，多項式時間で長さ $n$ のインスタンスの判定を行うことが可能，ということです．

分かり易い例でいうと充足可能性問題(SAT)の入力の $n$ 変数ブール論理式 $\phi(x_1,...,x_n)$ で与えられますが，もし $n-1$ 変数論理式を解くオラクルがあるとすれば， $n$ 変数論理式 $\phi$ の充足可能性判定も可能となります．具体的には $\phi$ から $\phi(0,x_2,x_3,...,x_n)$ と $\phi(1,x_2,x_3,...,x_n)$ のインスタンスを作ってオラクルに解かせれば良いわけです．オラクルがどちらか充足可能と判定したら $\phi$ は充足可能と判定できます．

もしNP=Pであった場合，この帰着を繰り返すことで論理式 $\phi$ に対して（もしあれば）充足割り当てを多項式時間で具体的に求めることができます．もちろん充足割り当てを見つける多項式時間探索アルゴリズムがあれば判定問題であるSATも多項式時間で解くこともできるので，SATの探索問題と判定問題のどちらか一方が多項式時間で解ければ他方も多項式時間で解けるという等価性があると言えます．SATはNP完全問題なので，任意のNP(判定)問題に対してその証拠の探索問題との等価性が言えることになります．

それでは非決定性指数時間計算可能クラス $\text{NEXP}=\bigcup_{c>0}\text{NTIME}(2^{n^c})$ ではどうでしょうか．一見（指数時間版の）降下型自己帰着を持ちそうに思えますが，実は詳しく見ると持たないことが分かります．したがってNEXPでは判定問題と探索問題の等価性は言えなくなってしまいます．もちろん探索版が解ける→判定版が解けるは言えますが，逆方向は少なくともNPと同じ議論ではダメです．

さて，なぜでしょうか？（と言いつつ後で詳しく書くつもりです．暇な人は考えてみて下さい．）