PSPACE完全(PSPACE-complete)とは、言語が多項式の空間で判定できるクラス $\mathrm{PSPACE}$ に属し、しかも $\mathrm{PSPACE}$ のどの言語もそれに多項式時間で還元できることをいう。$\mathrm{PSPACE}$ の中で最も難しい問題を表し、PSPACE完全な言語が 1 つでも多項式時間で判定できれば $\mathrm{P}=\mathrm{PSPACE}$ となる。代表例は、$\exists$ と $\forall$ で全変数を束縛した Boolean 論理式の真偽を問う TQBF で、再帰的な評価で多項式の空間に収まり、機械の計算の到達を中点で分ける論理式で書くことで困難性が示される。同じ構成から $\mathrm{PSPACE}=\mathrm{NPSPACE}$ も従う。
PSPACE完全(PSPACE-complete)な言語とは、多項式の大きさの記憶で判定できる言語のクラス $\mathrm{PSPACE}$ に属し、しかも $\mathrm{PSPACE}$ のどの言語もそれに多項式時間で還元できる言語のことである。NP完全 が $\mathrm{NP}$ の中で最も難しい問題を表すように、PSPACE完全な言語は $\mathrm{PSPACE}$ の中で最も難しい問題を表す。PSPACE完全な言語が 1 つでも多項式時間で判定できれば $\mathrm{P}=\mathrm{PSPACE}$ となり、とくに $\mathrm{P}=\mathrm{NP}$ も従う。
代表例は、すべての変数が「存在する」「すべての」で束縛された Boolean 論理式が真かどうかを問う問題 $\mathrm{TQBF}$ である。充足可能性問題 SAT が「$\exists x_1\cdots\exists x_n\,\varphi$ は真か」という問題であるのに対し、$\mathrm{TQBF}$ では $\exists$ と $\forall$ が交互に現れてよい。$\exists$ と $\forall$ の交代は、2 人のプレイヤーが交互に手を選ぶゲームで「先手にはある手があって、後手のどの手に対してもある手があって……先手が勝つ」と読める。このため、盤面を一般の大きさにしたゲームの必勝判定には PSPACE完全なものが多い。
この記事では、PSPACE困難・PSPACE完全を定義して基本性質を示し、主定理として $\mathrm{TQBF}$ の PSPACE完全性を証明する。その証明から $\mathrm{PSPACE}=\mathrm{NPSPACE}$ も従う。
計算のモデルとクラス $\mathrm{P}$・$\mathrm{NP}$・$\mathrm{PSPACE}$・$\mathrm{NPSPACE}$ は 計算量理論 の定義「多テープ Turing 機械と時間・空間」「計算量のクラス」に従う。$\mathrm{PSPACE}$ は、ある定数 $c\ge1$ について作業テープのマスを $c\,n^c+c$ 個以下しか使わない決定性の機械で判定できる言語の全体である(入力テープは読むだけで、使ったマスに数えない)。手続きは通常のプログラムの形で書く。変数とスタックに使う記憶が入力の長さの多項式で抑えられれば、多テープの機械でも多項式の空間で実行できるものとして扱う(計算量理論 の基本の包含関係の証明と同じ扱い)。グラフや論理式などは、有限の文字の語として標準的に符号化する。
定義は AB07 Definition 4.8 と同じである。還元を多項式時間に制限する理由は、還元そのものが $\mathrm{P}$ に収まる計算でなければ「$B$ が易しければ $A$ も易しい」という結論が出ないからである(反例の表の 1 行目)。
1:還元の写像 $f$ を時間 $q(n)$($q$ は多項式)で計算する機械をとると、$\lvert f(w)\rvert\le\lvert w\rvert+q(\lvert w\rvert)+1$ である(NP完全 の補題「出力の長さと機械の連結」)。$B$ を空間 $p(n)$ で判定する機械を $M_B$ とする。入力 $w$ に対し、$f(w)$ を作業テープに書き出し(空間 $O(\lvert w\rvert+q(\lvert w\rvert))$)、そのテープを入力とみなして $M_B$ を動かす。使う空間は $O(\lvert w\rvert+q(\lvert w\rvert))+p(\lvert w\rvert+q(\lvert w\rvert)+1)$ で、$\lvert w\rvert$ の多項式である。
2:$\mathrm{PSPACE}$ の言語 $L$ について $L\le_{\mathrm p}A$ と $A\le_{\mathrm p}B$ から、多項式時間の写像の合成により $L\le_{\mathrm p}B$ である(NP完全 の命題「還元の基本性質」の 1)。
3:$A$ を PSPACE完全とする。$A\in\mathrm{P}$ なら、$\mathrm{PSPACE}$ の任意の $L$ は $L\le_{\mathrm p}A$ なので、$f$ を計算してから $A$ の多項式時間の判定を動かせば $L\in\mathrm{P}$ である。$\mathrm{P}\subset\mathrm{PSPACE}$ と合わせて $\mathrm{P}=\mathrm{PSPACE}$ である。逆に $\mathrm{P}=\mathrm{PSPACE}$ なら $A\in\mathrm{PSPACE}=\mathrm{P}$ である。$\mathrm{NP}$ についても同じで、$A\in\mathrm{NP}$ なら、$w$ から $f(w)$ を決定的に計算してから $A$ の非決定性の機械を動かすことで $L\in\mathrm{NP}$ となり、$\mathrm{NP}\subset\mathrm{PSPACE}$(計算量理論 の定理「基本の包含関係」)と合わせて等号が成り立つ。$\square$
$\mathrm{PSPACE}$ の定義そのものを言語にすると、PSPACE完全な言語が 1 つ得られる。機械の記述 $\langle M\rangle$、入力 $w$、$1$ を $s$ 個並べた語 $1^s$ の組の符号化を $\langle M,w,1^s\rangle$ と書く。
$\mathrm{SPACETM}$ を、決定性の機械 $M$ が入力 $w$ に対し、作業テープのマスを合計 $s$ 個以下しか使わずに受理状態で停止するような組 $\langle M,w,1^s\rangle$ の全体とする。$\mathrm{SPACETM}$ は PSPACE完全である。
要点:$1^s$ が入力に含まれるので、$s$ 個のマスでの模倣は入力の長さに比例する空間で済む。困難性は、$L$ を判定する機械と空間の上限を還元の写像に書き込めばよい。
$\mathrm{SPACETM}\in\mathrm{PSPACE}$ を示す。入力 $x=\langle M,w,1^s\rangle$ の長さを $N$ とし、$M$ の状態の集合を $Q$、作業テープの文字を $\Gamma$、作業テープの本数を $k$ とする。使ったマスが $s$ 以下の様相は $K:=\lvert Q\rvert\,(\lvert w\rvert+2)\,(s\lvert\Gamma\rvert^s)^k$ 個以下である(計算量理論 の補題「様相の個数」)。$M$ の計算を 1 段ずつ模倣し、作業テープの内容とヘッドの位置を自分の作業テープに保つ。マスの使用が $s$ を超えたら拒否し、受理状態に入れば受理し、拒否状態に入るか段数が $K$ に達したら拒否する。マスを $s$ 個以下しか使わずに停止する計算は同じ様相を 2 度通らないので、$K$ 段未満で終わる。したがってこの手続きは $x\in\mathrm{SPACETM}$ を正しく判定する。保つものは $M$ の様相($O(s\cdot k\log\lvert\Gamma\rvert+\log\lvert w\rvert)$ ビット)と $K$ までの 2 進法のカウンタ($O(\log K)$ ビット)で、$\lvert Q\rvert,\lvert\Gamma\rvert,k\le N$、$s\le N$ だから、空間は $N$ の多項式である。
困難性を示す。$L\in\mathrm{PSPACE}$ を、作業テープのマスを $c\,n^c+c$ 個以下しか使わない決定性の機械 $M_L$ で判定する。写像 $w\mapsto\langle M_L,w,1^{c\lvert w\rvert^c+c}\rangle$ は $\langle M_L\rangle$ と $c$ が固定なので多項式時間で計算でき、$w\in L$ と、$M_L$ が $w$ を $c\lvert w\rvert^c+c$ 個以下のマスで受理することは同値である。よって $L\le_{\mathrm p}\mathrm{SPACETM}$ である。$\square$
$\mathrm{SPACETM}$ は定義をそのまま言い換えただけの言語である。PSPACE完全という概念が役に立つのは、次に示す $\mathrm{TQBF}$ のように、機械に言及しない自然な問題が PSPACE完全になるからである。
量化はすべて先頭にまとめた形(冠頭形)に限っている。限らない式も、量化された変数の名前を付け替えれば、真偽を変えずに多項式時間で冠頭形に直せる(AB07 p. 80 の脚注)。この記事の証明では、直し方を下の主定理の証明の段 4 で具体的に示す。証明の途中では量化が内側に現れる式も使うが、その真偽も、自由変数に値を入れたうえで式の組み立てに沿って定め、$\exists y\,B$ は $B$ の $y$ に $0$ か $1$ を入れた一方が真のとき、$\forall y\,B$ は両方が真のときに真とする。
$\psi_1=\forall x\,\exists y\,\bigl((x\vee y)\wedge(\neg x\vee\neg y)\bigr)$ は真である。行列 $(x\vee y)\wedge(\neg x\vee\neg y)$ は「$x\ne y$」を表し、どの $x$ にも $y:=1-x$ がとれる。量化の順序を入れ替えた $\psi_2=\exists y\,\forall x\,\bigl((x\vee y)\wedge(\neg x\vee\neg y)\bigr)$ は偽である。$y$ を 1 つ決めると、$x:=y$ で行列が偽になる。量化を $\forall x\,\forall y$ にした式も偽である(AB07 Example 4.9 と同じ式)。
SAT は、全部の量化が $\exists$ の場合の $\mathrm{TQBF}$ である。論理式 $\varphi(x_1,\dots,x_n)$ が充足可能であることは、$\exists x_1\cdots\exists x_n\,\varphi$ が真であることと同じだからである。同様に、恒真であることは $\forall x_1\cdots\forall x_n\,\varphi$ が真であることと同じである。
困難性の証明では、機械の 1 段の遷移を Boolean 論理式で書く。これは Cook–Levinの定理 の局所性の議論と同じ考え方である。
$M$ を、作業テープのマスを $S(n):=c\,n^c+c$ 個以下しか使わない(決定性または非決定性の)機械とする。次の性質をもつ多項式時間の手続きがある。入力 $w$(長さ $n$)から、整数 $m$($n$ の多項式)、$m$ 個の定数の列 $C_{\mathrm{start}}\in\{0,1\}^m$、変数の組 $C=(C_1,\dots,C_m)$、$C'=(C'_1,\dots,C'_m)$ を自由変数とする Boolean 論理式 $\mathrm{step}_w(C,C')$ と、$C$ を自由変数とする $\mathrm{acc}_w(C)$ を書き出し、
要点:様相を「状態・入力ヘッドの位置・各作業テープの各マスの記号とヘッドの有無」のビット列で書くと、1 回の遷移は、遷移の表の有限個の場合分けと、各マスについての局所的な条件の連言で書ける。
$S:=S(n)$ とおく。様相を次のビットで符号化する。状態を $\lceil\log_2(\lvert Q\rvert+1)\rceil$ ビットの番号、入力ヘッドの位置 $0,\dots,n+1$ を $\lceil\log_2(n+2)\rceil$ ビットの 2 進数、作業テープ $j$ のマス $p$($0\le p< S$)ごとに記号の番号のビットと「ヘッドがここにある」の 1 ビット。$m$ はこれらの合計で $O(S+\log n)$ である。ビット列 $C$ が様相の符号であるとは、状態と記号の番号が範囲内にあり、入力ヘッドの位置が $n+1$ 以下で、各作業テープでヘッドの印がちょうど 1 つあることをいい、これは各マスの条件と「ちょうど 1 つ」の条件(どの 2 マスも同時に印をもたない、かつ少なくとも 1 つ印がある)の連言で、大きさ $O(S^2)$ の論理式 $\mathrm{valid}(C)$ になる。
遷移 $\tau\in\delta$ ごとに、$C$ で $\tau$ が適用でき、適用した結果が $C'$ であることを表す式 $\mathrm{move}_\tau(C,C')$ を作る。$\tau$ が読む状態 $q$ と、各作業テープのヘッドの下の記号 $a_j$、入力の記号 $a_0$ を指定し、書く状態 $q'$、記号 $b_j$、動き $d_j\in\{-1,0,+1\}$ を指定するとする。(i) $C$ の状態が $q$、$C'$ の状態が $q'$。(ii) 各 $j$ と $p$ について「$C$ でヘッドが $p$ にあれば、$C$ のマス $p$ の記号は $a_j$、$C'$ のマス $p$ の記号は $b_j$、$C'$ のヘッドは $p+d_j$ にある($p+d_j$ が $0$ 以上 $S$ 未満であることも要求する)」と「$C$ でヘッドが $p$ になければ、$C'$ のマス $p$ の記号は $C$ と同じ」。(iii) 入力の記号は、位置 $r=0,\dots,n+1$ のうち $w$ のその位置の記号(両端の記号を含む)が $a_0$ であるものすべてについて「入力ヘッドの位置が $r$」を並べた選言で表す。(iv) 入力ヘッドの位置の 2 進数が $d_0$ だけ動くことは、$O(\log n)$ ビットの加減の式で書く。これらの連言の大きさは $S$ と $n$ の多項式である。$\mathrm{step}_w(C,C'):=\mathrm{valid}(C)\wedge\mathrm{valid}(C')\wedge\bigvee_{\tau\in\delta}\mathrm{move}_\tau(C,C')$ とし、$\mathrm{acc}_w(C):=\mathrm{valid}(C)\wedge(\text{状態が }q_{\mathrm{acc}})$ とする。$\delta$ は $M$ の有限集合で $w$ によらないので、これらを書き出すのは $n$ の多項式時間でできる。$\mathrm{step}_w$ の定義が 2 を満たすことは、各条件が遷移の定義(計算量理論 の定義「多テープ Turing 機械と時間・空間」)をそのまま書いたものであることから従う。$\square$
$\mathrm{TQBF}$ は PSPACE完全である。
AB07 Theorem 4.11 の主張で、同書の章末の注によれば Stockmeyer と Meyer による。証明の困難性の部分は、到達できるかどうかを「途中の様相 $Z$ がある」で 2 つに分ける 計算量理論 の Savitch の定理の証明と同じ考え方を、論理式で書いたものである。
段 1($\mathrm{TQBF}\in\mathrm{PSPACE}$)。閉じた $\psi=Q_1x_1\cdots Q_nx_n\,\varphi$ を入力とし、その長さを $N$ とする。手続き $\mathrm{EVAL}(i)$ を、$x_1,\dots,x_{i-1}$ に値 $b_1,\dots,b_{i-1}$ を入れた状態で $Q_ix_i\cdots Q_nx_n\,\varphi$ の真偽を返すものとして、次で定める。$i=n+1$ なら、$\varphi$ の変数に値を入れて評価する。$i\le n$ なら、$b_i:=0$ として $\mathrm{EVAL}(i+1)$ を呼び、その結果の 1 ビットだけを残して、$b_i:=1$ として $\mathrm{EVAL}(i+1)$ を呼ぶ。$Q_i=\exists$ なら 2 つの結果の論理和、$Q_i=\forall$ なら論理積を返す。def-pc-qbf の 3 の帰納的な定義と見比べれば、$i$ についての降順の帰納法で $\mathrm{EVAL}(i)$ が正しい真偽を返し、$\mathrm{EVAL}(1)$ が $\psi$ の真偽を返す。
記憶は、値の配列 $b_1,\dots,b_n$($n$ ビット)と、呼び出しの積み重ね(各段に $i$ と「いま 2 回目の呼び出しか」と 1 回目の結果。$n+1$ 段で各段 $O(\log N)$ ビット)と、$i=n+1$ での $\varphi$ の評価に使う記憶である。値の入った $\varphi$ の評価は、括弧の内側の部分式から順に値に置き換えていけば $N$ の多項式時間で、したがって多項式の空間でできる。2 回目の呼び出しは 1 回目と同じ記憶を使い直すので、全体の空間は $N$ の多項式である。
段 2(論理式 $\varphi_i$)。困難性を示す。$L\in\mathrm{PSPACE}$ を、作業テープのマスを $S(n)=c\,n^c+c$ 個以下しか使わない機械 $M$ で判定する。入力 $w$ に lem-pc-step を当てて $m$、$C_{\mathrm{start}}$、$\mathrm{step}_w$、$\mathrm{acc}_w$ を得る。$C,C'$ を $m$ 個の変数の組とし、$C=C'$ は $\bigwedge_{j=1}^m(C_j\leftrightarrow C'_j)$ の略記とする。$i=0,1,\dots,m$ について、自由変数が $C,C'$ の量化 Boolean 論理式 $\varphi_i(C,C')$ を
$$
\varphi_0(C,C'):=(C=C')\vee\mathrm{step}_w(C,C'),
$$
$$
\varphi_i(C,C'):=\exists Z\,\forall D\,\forall D'\,\Bigl[\bigl((D=C\wedge D'=Z)\vee(D=Z\wedge D'=C')\bigr)\to\varphi_{i-1}(D,D')\Bigr]
$$
で定める。ここで $Z,D,D'$ は各段で新しくとる $m$ 個の変数の組で、$\exists Z$ は $\exists Z_1\cdots\exists Z_m$ の略記である($\forall$ も同様)。
段 3($\varphi_i$ の意味)。$\{0,1\}^m$ を頂点とし $\mathrm{step}_w$ が真の組を辺とする有向グラフを $G_w$ とする。道の長さは辺の本数で、長さ $0$ の道($C=C'$)も数える。$i$ についての帰納法で、すべての $C,C'\in\{0,1\}^m$ について
$$
\varphi_i(C,C')\text{ が真}\iff G_w\text{ に }C\text{ から }C'\text{ への長さ }2^i\text{ 以下の道がある}
$$
を示す。$i=0$ は定義どおりである。$i\ge1$ とする。括弧の中の式は、$(D,D')$ が $(C,Z)$ か $(Z,C')$ のときにだけ $\varphi_{i-1}(D,D')$ を要求するので、$\forall D\,\forall D'[\cdots]$ は「$\varphi_{i-1}(C,Z)$ かつ $\varphi_{i-1}(Z,C')$」と同値である。帰納法の仮定から、$\varphi_i(C,C')$ は「ある $Z$ について、$C$ から $Z$ と $Z$ から $C'$ への長さ $2^{i-1}$ 以下の道がある」と同値である。長さ $\ell\le2^i$ の道 $C=Y_0,\dots,Y_\ell=C'$ があれば $Z:=Y_{\lfloor\ell/2\rfloor}$ で前半・後半の長さは $2^{i-1}$ 以下であり、逆に 2 本の道をつなげば長さ $2^i$ 以下の道になる。
段 4(冠頭形と大きさ)。$\varphi_i$ の各段の変数は新しくとったので、$\varphi_{i-1}$ の量化された変数は前提の式 $A_i:=(D=C\wedge D'=Z)\vee(D=Z\wedge D'=C')$ に現れない。値の範囲 $\{0,1\}$ は空でないので、$y$ が $A$ に現れなければ $A\to Qy\,B$ と $Qy\,(A\to B)$ は同値である。これを繰り返すと、$\varphi_m$ は
$$
\exists Z^{(m)}\forall D^{(m)}\forall D'^{(m)}\cdots\exists Z^{(1)}\forall D^{(1)}\forall D'^{(1)}\,\bigl[A_m\to\bigl(A_{m-1}\to\cdots\to(A_1\to\varphi_0(D^{(1)},D'^{(1)}))\cdots\bigr)\bigr]
$$
と同値な冠頭形になる($A_i$ は段 $i$ の変数で書いたもの)。量化された変数は $3m^2$ 個、各 $A_i$ の大きさは $O(m)$ なので、全体の大きさは $\varphi_0$ の大きさと $m^2$ の多項式(変数の番号の桁を含む)であり、$n$ の多項式である。
段 5(還元)。$C$ に定数 $C_{\mathrm{start}}$ を代入し、$C'$ を量化して
$$
\psi_w:=\exists C'\,\bigl[\mathrm{acc}_w(C')\wedge\varphi_m(C_{\mathrm{start}},C')\bigr]
$$
とする(段 4 と同じく量化を先頭に出す)。$\psi_w$ は閉じた式で、$w$ から多項式時間で書き出せる。$\psi_w$ が真であることは、受理状態の様相の符号 $C'$ で、$G_w$ で $C_{\mathrm{start}}$ から長さ $2^m$ 以下の道で到達できるものがあることと同値である。$\mathrm{step}_w$ は様相の符号の間にしか辺を張らないので、$C_{\mathrm{start}}$ から到達できる頂点は、$M$ の $w$ に対する計算の道の上の様相(使ったマスは $S(n)$ 以下)の符号である。$M$ が $w$ を受理すれば受理状態に至る道があり、同じ様相を 2 度通る部分を除けば長さは頂点の数 $2^m$ 未満になる。逆に $\psi_w$ が真なら $M$ には受理する道がある。よって $w\in L\iff\psi_w\in\mathrm{TQBF}$ であり、$L\le_{\mathrm p}\mathrm{TQBF}$ である。$\square$
段 2 の式で $\forall D\,\forall D'$ を使うのは大きさを抑えるためである。素朴に $\varphi_i(C,C'):=\exists Z\,(\varphi_{i-1}(C,Z)\wedge\varphi_{i-1}(Z,C'))$ とおくと、$\varphi_{i-1}$ を 2 回書くので大きさが段ごとに 2 倍になり、$\varphi_m$ の大きさは $2^m$ 程度になって多項式時間の還元にならない(ex-pc-size)。
段 2〜5 で $M$ が決定性であることは使っていない。したがって同じ構成で、非決定性の多項式空間の言語も $\mathrm{TQBF}$ に還元できる(AB07 §4.3.1)。
$\mathrm{NPSPACE}$ のすべての言語 $L$ について $L\le_{\mathrm p}\mathrm{TQBF}$ である。とくに $\mathrm{PSPACE}=\mathrm{NPSPACE}$ である。
前半は thm-pc-tqbf の証明の段 2〜5 を非決定性の機械 $M$ に当てたものである(lem-pc-step は非決定性の機械も含む)。後半:$L\in\mathrm{NPSPACE}$ なら $L\le_{\mathrm p}\mathrm{TQBF}$ と $\mathrm{TQBF}\in\mathrm{PSPACE}$、prop-pc-basic の 1 から $L\in\mathrm{PSPACE}$ である。逆の包含は決定性の機械が非決定性の機械の特別な場合であることによる。$\square$
$\mathrm{PSPACE}=\mathrm{NPSPACE}$ は 計算量理論 の系「Savitch の定理の帰結」でも示されている。ここでの証明は、Savitch の定理の再帰を論理式に移し、その評価を段 1 の手続きに任せたものと見ることができる。
閉じた $\psi=Q_1x_1\cdots Q_nx_n\,\varphi$ を盤面とする 2 人のゲームを考える。$i=1,2,\dots,n$ の順に、$Q_i=\exists$ なら先手が、$Q_i=\forall$ なら後手が $x_i$ の値を選ぶ。全部の値が決まったとき $\varphi$ が真なら先手の勝ち、偽なら後手の勝ちとする。先手の 戦略 は、それまでに選ばれた値の列から次の値を決める関数で、どの後手の選び方に対しても先手が勝つ戦略を 必勝戦略 という。
先手に必勝戦略があることと、$\psi$ が真であることは同値である。
$n$ についての帰納法で示す。$n=0$ では選ぶ値がなく、先手の勝ちは $\varphi$ が真であることと同じである。$n\ge1$ とし、$Q_1=\exists$ とする。先手に必勝戦略があれば、それが最初に選ぶ値 $b$ のあとの戦略は $\psi_{x_1=b}$ のゲームの必勝戦略なので、帰納法の仮定から $\psi_{x_1=b}$ は真で、$\psi$ は真である。逆に $\psi_{x_1=b}$ が真なら、最初に $b$ を選び、以後 $\psi_{x_1=b}$ の必勝戦略に従えばよい。$Q_1=\forall$ なら、先手に必勝戦略があることは、後手の最初の値 $b=0,1$ のどちらのあとにも先手に必勝戦略があることと同値で、帰納法の仮定から $\psi_{x_1=0}$ と $\psi_{x_1=1}$ がともに真であることと同値である。$\square$
したがって、論理式ゲームの必勝判定は PSPACE完全である(AB07 Example 4.13)。必勝戦略そのものは $2^n$ 通りの局面の答えを含みうるので、NP の証拠のように短く書けるとは限らない。盤面の大きさを一般にした Hex(一般化 Hex)の必勝判定が PSPACE完全であることは Even と Tarjan による(AB07 第 4 章の注、p. 88。この記事では証明しない)。
$\psi=\exists x\,\forall y\,\exists z\,\bigl[(x\vee z)\wedge(y\vee\neg z)\wedge(\neg x\vee\neg y\vee z)\bigr]$ の真偽を thm-pc-tqbf の証明の段 1 の手続きで求める。$x=1$ とすると行列は $(y\vee\neg z)\wedge(\neg y\vee z)$、すなわち $z=y$ となり、どの $y$ にも $z:=y$ がとれるので $\psi_{x=1}$ は真である。よって $\psi$ は真である。参考に $x=0$ では行列は $z\wedge(y\vee\neg z)$ で、$y=0$ のときどの $z$ でも偽なので、$\psi_{x=0}$ は偽である。手続きは最後の段で $\varphi$ を $2^3=8$ 通りの値で評価し、同時に保つ値は $x,y,z$ の 3 ビットと各段の結果の 1 ビットだけである。ゲームとしては、先手は $x=1$ を選び、後手の $y$ を見て $z:=y$ と答えれば勝つ。
様相の符号の長さを $m$ とする。thm-pc-tqbf の証明の $\varphi_m$ で量化される変数は各段 $3m$ 個、$m$ 段で $3m^2$ 個である。$m=10$ なら $300$ 個、$m=40$ なら $4800$ 個である。素朴な再帰 $\varphi_i=\exists Z\,(\varphi_{i-1}(C,Z)\wedge\varphi_{i-1}(Z,C'))$ では $\varphi_0$ が $2^m$ 回書かれ、$m=10$ で $1024$ 回、$m=40$ で $2^{40}\approx1.10\times10^{12}$ 回になる。
thm-pc-tqbf と prop-pc-basic は、還元が多項式時間であること、量化が交代しうること、構成した論理式の大きさが多項式であることに依存する。表の各行は、条件を 1 つだけ外した場合である。
| 外す条件 | 例 | 成り立たなくなる結論 |
|---|---|---|
| 還元が多項式時間 | 指数時間の還元を許すと、$\mathrm{PSPACE}$ の $L$ は $w\in L$ なら $1$、そうでなければ $0$ を返す写像で $\{1\}$ に還元される($\mathrm{PSPACE}\subset\mathrm{EXP}$ による) | $\mathrm{P}$ に属する $\{1\}$ が「困難」になり、prop-pc-basic の 3 の論法(還元してから多項式時間で判定する)が使えない |
| 完全の定義の $B\in\mathrm{PSPACE}$ | 停止問題は PSPACE困難だが、計算可能でないので $\mathrm{PSPACE}$ に属さない(ex-pc-halt) | 「PSPACE困難な言語は多項式の空間で判定できる」 |
| 完全の定義の PSPACE困難 | 空集合 $\emptyset$ は $\mathrm{PSPACE}$ に属するが、空でない言語は $\emptyset$ に還元できない($w\in L$ なら $f(w)\in\emptyset$ となって矛盾) | 「$\mathrm{PSPACE}$ の言語はどれも PSPACE完全」 |
| 量化に $\forall$ を含みうる | 全部の量化が $\exists$ の式に限ると、真偽の判定は SAT で、NP に属する(NP完全) | 制限した言語には thm-pc-tqbf の困難性の証明が使えない(困難性が偽と示されたわけではない)。この制限した言語が PSPACE完全なら $\mathrm{NP}=\mathrm{PSPACE}$ が従う(prop-pc-basic の 3) |
| 論理式の大きさが多項式 | 素朴な再帰 $\exists Z\,(\varphi_{i-1}(C,Z)\wedge\varphi_{i-1}(Z,C'))$(ex-pc-size) | 大きさが $2^m$ 程度になり、写像が多項式時間で計算できない |
停止問題 $\mathrm{HALT}$ を、機械 $M$ が入力 $x$ で停止するような組 $\langle M,x\rangle$ の全体とする(停止問題)。$L\in\mathrm{PSPACE}$ を、どの入力でも停止する機械 $M_L$ で判定し、$M_L$ の拒否状態に入る代わりに同じ状態にとどまり続けるように変えた機械を $M'_L$ とする。$M'_L$ は $w\in L$ のときだけ停止するので、$w\mapsto\langle M'_L,w\rangle$ は $L$ から $\mathrm{HALT}$ への還元であり、$\langle M'_L\rangle$ が固定なので多項式時間で計算できる。$\mathrm{HALT}$ は計算可能でない(停止問題)ので、$\mathrm{PSPACE}$ に属さない。
| 誤り | 正しくは | なぜ |
|---|---|---|
| PSPACE完全な問題は多項式時間で解けないことが証明されている | $\mathrm{P}=\mathrm{PSPACE}$ かどうかは AB07 の時点(2007 年)で知られていない(p. 79) | 分かっているのは「1 つでも多項式時間で解ければ $\mathrm{P}=\mathrm{PSPACE}$」まで(prop-pc-basic) |
| $\mathrm{TQBF}$ は SAT の一般化なので NP に属する | 属すれば $\mathrm{NP}=\mathrm{PSPACE}$ となる | 真であることの証拠が短く書けるとは限らない(prop-pc-basic の 3) |
| 評価の再帰は $2^n$ 通りの値を覚えるので指数の空間が要る | 2 つの再帰呼び出しは同じ記憶を使い直し、空間は多項式 | thm-pc-tqbf の証明の段 1 |
| 量化を先頭に出すとき変数の名前を気にしない | $(\exists x\,A)\wedge B$ で $x$ が $B$ に現れるなら、先に $x$ を新しい名前に替える | 段 4 は各段の変数を新しくとることに依存する |
$\mathrm{P}\subset\mathrm{NP}\subset\mathrm{PSPACE}$ なので、$\mathrm{P}=\mathrm{PSPACE}$ なら $\mathrm{P}=\mathrm{NP}$ である。多項式階層 $\mathrm{PH}$ も $\mathrm{PSPACE}$ に含まれる(戸田の定理(計算量))。PSPACE は対話証明でも特徴づけられ、$\mathrm{IP}=\mathrm{PSPACE}$ である(IP=PSPACE。対話証明の定義は ゼロ知識証明 の節「対話証明」にもある)。その証明でも $\mathrm{TQBF}$ が中心の役割を果たし、IP=PSPACE の定理「TQBF の対話証明」で TQBF の対話証明を作ることが $\mathrm{PSPACE}\subset\mathrm{IP}$ の要になる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する