♥ 縞模様を超えて

P と NP は複雑性クラスの巨大な階層における最初の二ステップでしかありません。この章 (そしてこの本) の締めくくりとして、興味深い複雑性クラスをいくつか紹介します。

多項式空間

PSPACE は多項式空間を使って解ける判定問題の集合です。NP に属する全ての問題 (したがって P に属する全ての問題) は PSPACE に属します。NP \(\neq\) PSPACE であることが広く信じられていますが、P \(\neq\) PSPACE さえ証明できた人はいません。

問題 \(\Pi\) がPSPACE 困難 (PSPACE-hard) であるとは、多項式空間を使って解ける任意の問題 \(\Pi^{\prime}\) について \(\Pi^{\prime}\) から \(\Pi\) への多項式時間多対一帰着が存在することを言います。PSPACE 困難な問題が一つでも NP に属すれば PSPACE=NP であり、同様に PSPACE 困難な問題が一つでも P に属すれば P=PSPACE です。

一番重要な PSPACE 困難問題は量化子付きブール式問題 (quantified boolean formula problem, \(\textsc{QBF}\)) です。これは任意の数の全称量化子および存在量化子のついた自由変数を含まないブール式 \(\Phi\) が \(\textsc{True}\) に等しいかを判定する問題であり、例えば \(\textsc{SAT}\) は存在量化子だけを含む \(\textsc{QBF}\) の特殊ケースとみなすことができます。また次の式は \(\textsc{QBF}\) への正しい入力です: \[ ∃a: ∀b: ∃c: (∀d : a ∨ b ∨ c ∨ \overline{d}) ⇔ ((b ∧ \overline{c}) ∨ (∃e : \overline{(\overline{a} ⇒ e)} ∨ (c \neq a ∧ e))) \] \(\forall\) と \(\exists\) が一つずつ交互に式の先頭にだけついている連言標準形の式だけを考えたとしても、\(\textsc{QBF}\) は PSPACE 困難となります。例えば次の式です: \[ ∃a: ∀b: ∃c: ∀d :(a ∨ b ∨ c) ∧ (b ∨ \overline{c} ∨ \overline{d}) ∧ (\overline{a} ∨ c ∨ d) ∧ (a ∨ \overline{b} ∨ \overline{d}) \]

この制限されたバージョンの QBF は二人のプレイヤーの間の質問ゲームとしても表現できます。つまり二人のプレイヤー Alice と Bob に自由変数 \(x_{1}, x_{2}, \ldots, x_{n}\) を持つ 3CNF 式が与えられ、二人が交互に変数に真偽値を割り当てていくというゲームです ――まず Alice が \(x_{1}\) に割り当て、次に Bob が \(x_{2}\) に割り当て、以下同様です。Alice は式全体が \(\textsc{True}\) になるように値を割り当て、Bob は式全体が \(\textsc{False}\) になるように変数に値を割り当てます。Alice と Bob が完璧にプレイするという仮定の下で誰が勝つかを答える問題は、\(\textsc{QBF}\) と同じ問題になります。

驚くことではないかもしれませんが、三目並べ、オセロ、チェッカー、囲碁、チェス、マンカラなどのほとんどの二人対戦ゲーム¹ ――正確にはこれらのゲームを任意に大きい盤で遊べるようにしたもの―― は PSPACE 困難です。

もう一つの重要な PSPACE 困難問題は NFA の全域性です:「あるアルファベット \(\Sigma\) 上の非決定性有限状態オートマトン \(M\) が与えられたとする。\(M\) は \(\Sigma^{\ast}\) に含まれる全ての文字列を受理するか？」という問題です。NFA の同値性 (「二つの NFA は同じ言語を受理するか？」) と NFA の最小化 (「ある NFA と同じ言語を受理する最小の NFA は何か？」) という似た問題もまた PSPACE 困難であり、これらの問題に対応する正規表現の問題も PSPACE 困難となります (決定性有限状態オートマトンに対する同じ問題は多項式時間で解けます)。

指数時間

次に紹介する巨大な複雑性クラスは、指数時間で解ける判定問題を集めた EXP (あるいは EXPTIME) です。これはある \(c > 0\) があって \(2^{n^{c}}\) ステップで問題が解けることを意味します。PSPACE に含まれる全ての問題 (したがって NP に含まれる全ての問題 (したがって P に含まれる全ての問題)) は EXP にも属します。PSPACE \(\subsetneq\) EXP であると広く信じられていますが、NP \(\neq\) EXP さえ証明できた人はいません。

問題 \(\Pi\) がEXP 困難 (EXP-hard) であるとは、指数時間を使って解ける任意の問題 \(\Pi^{\prime}\) について \(\Pi^{\prime}\) から \(\Pi\) への多項式時間多対一帰着が存在することを言います。EXP 困難な問題が一つでも PSPACE に属すれば EXP=PSPACE であり、同様に EXP 困難な問題が一つでも NP に属すれば EXP=NP です。ただし P \(\neq\) EXP であることは分かっているので、EXP 困難な問題は P に属しません。

興味深い二人対戦ゲームの多く ――チェッカー、チェス、マンカラ、囲碁など―― を一般化したものは EXP 困難となりますが、PSPACE 困難と EXP 困難の境界はとても繊細です。例えば通常の \(8 \times 8\) のチェスには引き分けになる状況が三種類あります:

1. ステールメイト (チェックされていないプレイヤーに合法手が無い)
2. 三度同じ盤面になる
3. 50 手の間両者の駒が取られない

\(n \times n\) に一般化したチェスが PSPACE 困難かそれとも EXP 困難かはこの引き分けのルールをどう一般化するかによって変化します。例えば \(n^{3}\) 手の間両者の駒が取られなければ引き分けというルールを採用した場合、全てのゲームが多項式回の手で終了するので、多項式空間だけを使って全てのゲームをシミュレートできます。一方で、両者が駒を取らない状況がどれだけ長く続いても引き分けにならないというルールを採用した場合、一つのゲームが指数回の手に及ぶことになり、多項式空間だけでは同じ盤面になったかどうかを検出できません。実はこのバージョンの \(n \times n\) チェスは EXP 困難となります。

もっと高く！

もちろん、指数時間だって話の終わりではありません。 NEXP は非決定的指数時間で解ける判定問題の集合です。NEXP に含まれる問題の答えが \(\textsc{Yes}\) であるインスタンスには答が \(\textsc{Yes}\) であることの証明が存在して、その証明が指数時間で検証できるということです。 EXPSPACE は指数空間を使って解ける判定問題の集合です。これらの巨大な複雑性クラスにさえ困難な問題が存在します。例えば正規表現に交差演算子 \(\cap\) を加えた場合、二つの正規表現が同じ言語を表しているかどうかを判定する問題は EXPSPACE 困難です。

EXPSPACE よりも大きな複雑性クラスも存在し、資源の制限が二重指数 (doubly-exponential) であるもの (EEXP, NEEXP, EEXPSPACE)、三重指数 (triply-exponential) であるもの (EEEXP, NEEEXP, EEEXPSPACE) と無限に続きます。

ここまでに話してきた複雑性クラスは包含関係による順序を持ちます: \[ \text{P} ⊆ \text{NP} ⊆ \text{PSPACE} ⊆ \text{EXP} ⊆ \text{NEXP} ⊆ \text{EXPSPACE} ⊆ \text{EEXP} ⊆ \text{NEEXP} ⊆ ··· \] ほとんどの複雑性理論研究者はこれら包含関係全てが真の包含関係である、つまりどの二つの複雑性クラスも同じではないと強く信じています。しかし、これまでに示された一番強い結果でも、この並びで三つ離れたクラスが異なることを示すに留まっています。例えば P \(\neq\) EXP および PSPACE \(\neq\) EXPSPACE は示されていますが、P \(\neq\) PSPACE および NP \(\neq\) EXP は示されていません。

指数を使って表せる複雑性クラスの増加列の極限は ELEMENTARY と呼ばれる複雑性クラスであり、このクラスは時間または空間の使用量が定数 \(k\) を使って \(2 \uparrow^{k} n\) で抑えられる判定問題の集合として定義できます。ここで \[ 2 \uparrow^{k} n := \begin{cases} n & \text{if } k = 0 \\ 2^{2 \uparrow^{k-1} n} & \text{それ以外} \end{cases} \] であり、例えば \(2 \uparrow^{1} n = 2^{n}\) および \(2 \uparrow^{2} n = 2^{2^{n}}\) です。

全ての自然な判定問題がこの初等時間 (elementary time) で解けると思いたくなるかもしれませんが、そうではありません。拡張正規表現と呼ばれる、 (空でも構わない) アルファベットを結合 (\(xy\))、和集合 \(x + y\)、Kleene 閉包 (\(x^\ast\))、否定 (\(\overline{x}\)) で組み合わせたものを考えます。例えば \(\overline{({\color{maroon}{0}} + {\color{maroon}{1}})^{\ast} \color{maroon}{00} ({\color{maroon}{0}}+{\color{maroon}{1}})^{\ast}}\) という拡張正規表現は \(\lbrace {\color{maroon}{0}}, {\color{maroon}{1}} \rbrace\) が並んだ文字列であって \({\color{maroon}{0}}\) が連続して出現しないものを表します。二つの拡張正規表現が表す言語が等しいかどうかをアルゴリズムを使って判定するのは可能であり、具体的には二つの拡張正規表現を同値な NFA で表し、DFA に変換し、DFA を最小化して比べれば判定できます。しかしこのアルゴリズムの実行時間は式の中に否定が出現するたびに指数的に増加するので \(2 \uparrow^{\Theta(n)} 2\) であり、初等的ではありません。1974 年の Larry Stockmeyer (ラリー・ストックメイヤー) の証明によると、Kleene 閉包を使用を禁止したとしてもこの問題は初等時間で解くことができません！

1. ゲームとパズルの計算複雑性に関する結果の優れた (しかし古くなりつつあるのも事実な) まとめについては、Erik Demaine と Bob Hearn による Games, Puzzles, and Computation を参照してください。^[return]