計算量クラスの包含関係と完全問題

$NL \subseteq P \subseteq NP \subseteq PSPACE \subseteq EXP$ 、サヴィッチの定理 $PSPACE = NPSPACE$ 、イマーマン・セレプチェニの定理 $NL = coNL$ 、時間・領域階層定理（ $P ⊊ EXP$ , $NL ⊊ PSPACE$ ）と、NP 完全・PSPACE 完全（ $TQBF$ ）の帰結を使って、証明済みの主張と未解決の主張を判定できる

前提

多項式時間多対一帰着の性質（大学院数学計算理論・ラムダ計算）

この技能までの道筋（22 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

決定性有限オートマトンの動作と受理判定（大学数学オートマトン・形式言語）
チューリング機械の動作の追跡（大学数学オートマトン・形式言語）
四則の混じった計算の順序（算数計算と数のきまり）
等間隔にならんだ数の和（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）
計算量のオーダーの比較（大学数学アルゴリズムと計算量）
多項式時間多対一帰着の性質（大学院数学計算理論・ラムダ計算）

説明

計算量クラスの間には、証明されている包含・一致・真の包含と、まだ誰も証明できていない（未解決の）関係とが入り混じっています。この技能では、包含の鎖 $NL \subseteq P \subseteq NP \subseteq PSPACE \subseteq EXP$ 、サヴィッチの定理 $PSPACE = NPSPACE$ 、イマーマン・セレプチェニの定理 $NL = coNL$ 、階層定理による $P ⊊ EXP$ , $NL ⊊ PSPACE$ を道具として、与えられた主張が「証明済み」か「未解決」かを判定します。さらに、NP 完全問題や PSPACE 完全問題 $TQBF$ がどこかのクラスに入ったと仮定したときに何が従うかも読み取れるようになります。

なぜそうしてよいのか

まずクラスを確認します。 $NL$ は非決定性チューリング機械で $O (lo g n)$ の作業領域で判定できる言語全体、 $P$ ・ $NP$ は決定性・非決定性の多項式時間、 $PSPACE$ ・ $NPSPACE$ は決定性・非決定性の多項式領域、 $EXP = ⋃_{k} TIME (2^{n^{k}})$ です。クラス $C$ に対し $co C = {L : L \in C}$ とします。包含の鎖の理由は「様相（状態・ヘッド位置・テープ内容の組）の個数」です。領域 $O (lo g n)$ の機械の様相は $2^{O (l o g n)} = n^{O (1)}$ 個しかないので、様相のグラフで受理様相に到達できるかを多項式時間で探索でき $NL \subseteq P$ 。 $P \subseteq NP$ は決定性が非決定性の特別な場合だから。 $NP \subseteq PSPACE$ は、多項式長の証拠を 1 つずつ同じ領域を使い回して全部試せるから。 $PSPACE \subseteq EXP$ は、多項式領域の機械の様相が $2^{poly (n)}$ 個しかなく、停止する計算は同じ様相をくり返さないので、その歩数以内に必ず止まるからです。

一致と真の包含も整理しておきます。サヴィッチの定理は「非決定性の領域 $s (n)$ は決定性の領域 $s (n)^{2}$ で模倣できる」（ $s (n) \geq lo g n$ ）というもので、多項式の 2 乗も多項式なので $NPSPACE = PSPACE$ 。イマーマン・セレプチェニの定理は「到達できない」ことも非決定性の対数領域で確かめられることを示し、 $NL = coNL$ を与えます。時間階層定理は「時間を十分多く与えると真に多くの言語が判定できる」ことを対角線論法で示し $P ⊊ EXP$ 、領域階層定理とサヴィッチの定理（ $NL \subseteq SPACE (lo g^{2} n) ⊊ SPACE (n) \subseteq PSPACE$ ）から $NL ⊊ PSPACE$ が出ます。ここで大切なのは、鎖の両端が異なると証明されていても、途中のどこが真の包含かはわからないことです。 $P ⊊ EXP$ から言えるのは「 $P ⊊ NP$ , $NP ⊊ PSPACE$ , $PSPACE ⊊ EXP$ の少なくとも 1 つが成り立つ」までで、どれが成り立つかは未解決です。

完全問題は帰着の性質から結論を引き出します。 $B$ が $C$ 完全とは、 $B \in C$ かつすべての $A \in C$ について $A \leq_{p} B$ であることです。すると「 $A \leq_{p} B$ かつ $B \in P$ なら $A \in P$ 」から、 $B \in P$ なら $C \subseteq P$ が従います。たとえば $TQBF$ （量化子付きブール式の真偽）は $PSPACE$ 完全なので、 $TQBF \in P$ なら $P = PSPACE$ 、 $TQBF \in NP$ なら $NP = PSPACE$ です。ただし $TQBF \in / P$ 自体は証明されていません。

手順

主張を「包含 $\subseteq$ 」「一致 $=$ 」「真の包含 $⊊$ （ $\neq =$ ）」のどれかの形に直し、現れるクラスを鎖 $NL \subseteq P \subseteq NP \subseteq PSPACE \subseteq EXP$ の上に置く
包含なら鎖から、一致ならサヴィッチの定理（ $PSPACE = NPSPACE$ ）・イマーマン・セレプチェニの定理（ $NL = coNL$ ）で証明済みかを確かめる
真の包含は、階層定理で直接示されている $P ⊊ EXP$ , $NL ⊊ PSPACE$ （とそこから鎖でわかること）だけが証明済み。隣り合うクラスの分離（ $P$ 対 $NP$ など）は未解決とする
「少なくとも 1 つは異なる」形の主張は、両端が異なること（例: $P \neq = EXP$ ）と、途中がすべて等しいと両端も等しくなることから判定する
完全問題についての仮定は、「 $B$ が $C$ 完全で $B \in D$ （ $D$ は $\leq_{p}$ で閉じたクラス）なら $C \subseteq D$ 」に当てはめて帰結を読む

例題

次の主張のうち、現在までに証明されているものをすべて選べ。

ア　 $P \neq = EXP$
イ　 $P \neq = NP$
ウ　 $NL \neq = PSPACE$
エ　 $P ⊊ NP$ , $NP ⊊ PSPACE$ , $PSPACE ⊊ EXP$ の少なくとも 1 つが成り立つ
オ　 $NP = coNP$
カ　 $NPSPACE = PSPACE$

例題の解答

【手順 1】各主張を形で分ける。ア・イ・ウは真の包含（鎖上で $P \subseteq EXP$ , $P \subseteq NP$ , $NL \subseteq PSPACE$ なので $\neq =$ は $⊊$ と同じ）、エは「少なくとも 1 つ」の形、オ・カは一致の形。

【手順 2】カはサヴィッチの定理そのものなので証明済み。オの $NP = coNP$ は、これを与える定理がなく未解決（イマーマン・セレプチェニの定理は対数領域の $NL = coNL$ であり、多項式時間の $NP$ には及ばない）。

【手順 3】アは時間階層定理、ウは領域階層定理（とサヴィッチの定理）で証明済み。イは隣り合う $P$ と $NP$ の分離で未解決。

【手順 4】エ：もし 3 つとも成り立たなければ $P = NP = PSPACE = EXP$ となり、ア $P \neq = EXP$ に反する。よってエは証明済み（どれが成り立つかは未解決だが、主張は「少なくとも 1 つ」なので正しい）。

以上より、証明済みのものはア, ウ, エ, カ。

答え:

ア, ウ, エ, カ

よくある誤り

鎖の途中の分離が未解決だから、両端の $P \neq = EXP$ も未解決だとしてしまう誤り。正しくは時間階層定理で $P ⊊ EXP$ は証明済みで、未解決なのは $P ⊊ NP$ などどこで真に大きくなるかのほうである。
$NL = coNL$ や $PSPACE = NPSPACE$ と同じ理屈で $NP = coNP$ や $P = NP$ も成り立つとしてしまう誤り。サヴィッチの定理とイマーマン・セレプチェニの定理は領域を使い回せることに頼った領域計算量の結果で、時間計算量の $P$ 対 $NP$ 、 $NP$ 対 $coNP$ はどちらも未解決である。
サヴィッチの定理から $NL = L$ （ $L$ は決定性対数領域）が出るとしてしまう誤り。サヴィッチの定理で得られるのは $NL \subseteq SPACE (lo g^{2} n)$ までで、 $(lo g n)^{2}$ は $O (lo g n)$ ではないので、 $L = NL$ は未解決である。
$TQBF$ が $PSPACE$ 完全だから $TQBF \in / P$ は証明済みだとしてしまう誤り。完全性から言えるのは「 $TQBF \in P ⟺ P = PSPACE$ 」までで、 $P = PSPACE$ かどうかは未解決なので、 $TQBF \in / P$ も未解決である。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
関数 $f (n)$ に対し、 $SPACE (f (n))$ は決定性チューリング機械で領域 $O (f (n))$ で判定できる言語のクラス、 $NSPACE (f (n))$ は非決定性チューリング機械で領域 $O (f (n))$ で判定できる言語のクラス、 $coNSPACE (f (n)) = {A ∣ A \in NSPACE (f (n))}$ とする。また $NL = NSPACE (lo g n)$ 、 $coNL = coNSPACE (lo g n)$ とし、 $P, PSPACE, NPSPACE, EXP$ は標準的な定義（多項式時間・多項式領域・非決定性多項式領域・決定性指数時間 $2^{n^{O (1)}}$ ）に従うものとする。 $⊊$ は真の包含を表す。
次のア〜カの主張は、いずれもサヴィッチの定理・イマーマン–セレプチェニの定理・領域階層定理・時間階層定理によって、正しいか誤りかが確定する。このうち正しいものをすべて選べ。
ア　 $NL ⊊ PSPACE$
イ　 $NPSPACE \subseteq PSPACE$
ウ　 $P = EXP$
エ　 $NL = coNL$
オ　 $SPACE (n) = SPACE (n^{2})$
カ　 $NSPACE (n) = coNSPACE (n)$

計算量クラスの包含関係と完全問題

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題