多項式階層

同義語:polynomial hierarchypolynomial-time hierarchy

概要

多項式階層(polynomial hierarchy)とは、多項式時間で判定できる条件の前に、長さが多項式の列についての存在と全称の量化子を定数回交代させて付けた形で書ける言語のクラス $\Sigma_k^{\mathrm p},\Pi_k^{\mathrm p}$ の列と、その和 $\mathrm{PH}$ である。第 1 段は $\mathrm{NP}$ と $\mathrm{coNP}$ で、$\mathrm P$ 対 $\mathrm{NP}$ 問題を一般化する。ある段で $\Sigma_k^{\mathrm p}=\Pi_k^{\mathrm p}$ なら階層はその段で潰れ、$\mathrm P=\mathrm{NP}$ なら $\mathrm{PH}=\mathrm P$ となる。各段には完全問題があり、$\mathrm{PH}$ は PSPACE に含まれる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: NP完全, Cook–Levinの定理

グラフ $G$ と整数 $k$ について「$G$ に大きさ $k$ の独立集合がある」かどうかは NP の問題である。独立集合そのものを示せば、それが正しいことは多項式時間で確かめられる。では「$G$ の独立集合の最大の大きさがちょうど $k$ である」かどうかはどうか。大きさ $k$ の独立集合を示すだけでは足りず、「大きさ $k+1$ の独立集合はどれもない」ことも確かめなければならない。この条件は「ある $S$ について、すべての $T$ について…」と、存在と全称の量化子を 1 回ずつ交代させて書ける。
多項式階層(polynomial hierarchy)は、多項式時間で確かめられる条件の前に、長さが多項式の列についての $\exists$ と $\forall$ を定数回交代させて付けた言語のクラスの列 $\Sigma_k^{\mathrm p},\Pi_k^{\mathrm p}$ と、その和 $\mathrm{PH}$ である。第 1 段が NP と coNP で、P 対 NP 問題を一般化する枠組みになる。この記事では定義と基本性質を述べ、主定理「ある段で $\Sigma_k^{\mathrm p}=\Pi_k^{\mathrm p}$ なら階層はその段で潰れる」を完全に証明する。さらに、各段の完全問題、$\mathrm{PH}\subset\mathrm{PSPACE}$、神託による言い換えを述べる。

定義

言語は $\{0,1\}^*$ の部分集合とし、P・NP・多項式時間還元 $\le_{\mathrm p}$ は NP完全 の定義に従う。列の組 $(x,u_1,\dots,u_k)$ は、長さが成分の長さの和の定数倍以内になるように 1 つの列に符号化して算法に渡す。言語 $L$ の補集合 $\{0,1\}^*\setminus L$ を $\overline L$、クラス $\mathcal C$ の言語の補集合の全体を $\mathrm{co}\mathcal C$ と書く。

多項式階層

$k\ge1$ とする。言語 $L$ が $\Sigma_k^{\mathrm p}$ に属するとは、多項式時間の決定的な算法 $M$(値は $0$ か $1$)と多項式 $q$ があって、すべての $x$ について
$$ x\in L\iff\exists u_1\,\forall u_2\,\exists u_3\cdots Q_ku_k\ \ M(x,u_1,\dots,u_k)=1 $$
となることをいう。ここで各 $u_i$ は $\{0,1\}^{q(\lvert x\rvert)}$ を動き、$Q_k$ は $k$ が奇数なら $\exists$、偶数なら $\forall$ である。量化子を $\forall u_1\,\exists u_2\cdots$ と $\forall$ から始めたものを $\Pi_k^{\mathrm p}$ とする。$\Sigma_0^{\mathrm p}=\Pi_0^{\mathrm p}:=\mathrm P$ とし、
$$ \mathrm{PH}:=\bigcup_{k\ge0}\Sigma_k^{\mathrm p} $$
を 多項式階層 という(AB07 Definition 5.4、p. 93)。

$\Sigma_1^{\mathrm p}$ は NP の証明書による定義そのもので $\Sigma_1^{\mathrm p}=\mathrm{NP}$、同様に $\Pi_1^{\mathrm p}=\mathrm{coNP}$ である。以下、誤解のないときは $\Sigma_k,\Pi_k$ と書く。

基本性質

$k\ge0$ とする。

  1. $\Pi_k=\mathrm{co}\Sigma_k$ である。
  2. $\Sigma_k\cup\Pi_k\subset\Sigma_{k+1}\cap\Pi_{k+1}$ である。
  3. def-ph-def で、各 $u_i$ の長さを「$q(\lvert x\rvert)$ 以下」としても、量化子の列を「$\exists$ から始まり、同じ量化子が続く箇所を 1 つと数えて $k$ 個の塊になる任意の列」としても、定まるクラスは変わらない。
  4. $A\le_{\mathrm p}B$ かつ $B\in\Sigma_k$ なら $A\in\Sigma_k$ である。$\Pi_k$ についても同じである。
証明を開く

1. $\neg\exists u\,\varphi\iff\forall u\,\neg\varphi$ と $\neg\forall u\,\varphi\iff\exists u\,\neg\varphi$ を $k$ 回使うと、$x\notin L$ は量化子をすべて入れ替え、$M$ を $1-M$ に替えた式で表される。

2. $L\in\Sigma_k$ の式の最後に、$M$ が読まない変数 $u_{k+1}$ の量化子を付ければ $\Sigma_{k+1}$ の形、最初に読まない変数の $\forall u_0$ を付ければ $\Pi_{k+1}$ の形になる。$\Pi_k$ も同様である。$k=0$ では $M(x)$ の前に読まない変数を置けばよい。

3. 同じ量化子の連続 $\exists u\,\exists u'$ は、組 $uu'$ についての $\exists$ 1 つにまとめられ、$\forall$ も同じである。長さをそろえるには、すべての塊を長さ $Q(\lvert x\rvert)$(長さの多項式の和)に延ばし、余分のビットを $M$ に読ませなければよい。長さが「$q(\lvert x\rvert)$ 以下」の列 $u$ は、$u10\cdots0$ の形の長さ $q(\lvert x\rvert)+1$ の列で表す。この形でない列について、$M$ は $\exists$ の塊なら $0$、$\forall$ の塊なら $1$ を返すとすれば(形の誤りは最初のものだけを見る)、形の正しい列についての量化と同値になる。

4. 還元 $f$ が多項式 $r$ の時間で計算できるとすると $\lvert f(x)\rvert\le r(\lvert x\rvert)$ で、$x\in A\iff f(x)\in B\iff\exists u_1\cdots M(f(x),u_1,\dots)=1$ である。$q$ を係数が非負の多項式にとると単調なので、$u_i$ の長さは $q(\lvert f(x)\rvert)\le q(r(\lvert x\rvert))$ である。長さが $q(\lvert f(x)\rvert)$ でない列を 3 の証明と同じく形の誤りとして扱えば、3 により「$q(r(\lvert x\rvert))$ 以下」として扱え、$x\mapsto M(f(x),\dots)$ は多項式時間である。$\square$

この補題の 2 と、後の prop-ph-pspace から、階層は次のように入れ子になっている。
$$ \mathrm P=\Sigma_0\subset\Sigma_1\cap\Pi_1\subset\Sigma_1\cup\Pi_1\subset\Sigma_2\cap\Pi_2\subset\Sigma_2\cup\Pi_2\subset\cdots\subset\mathrm{PH}\subset\mathrm{PSPACE}. $$
AB07(2007 年の版)の時点で、これらのどの包含についても真の包含かどうかは分かっていない($\mathrm P\ne\mathrm{PSPACE}$ も未解決である)。
使える条件:

  • (i) 内側の算法 $M$ は多項式時間である。
  • (ii) 量化する列の長さは $\lvert x\rvert$ の多項式でおさえられる。
  • (iii) 量化子の塊の個数 $k$ は入力によらない定数である。
  • (iv) 完全性は多項式時間還元で測る。

主定理:同じ段で等しければ階層は潰れる

多項式階層の崩壊

ある $k\ge1$ で $\Sigma_k=\Pi_k$ ならば、すべての $j\ge k$ で $\Sigma_j=\Pi_j=\Sigma_k$ であり、$\mathrm{PH}=\Sigma_k$ である(AB07 Theorem 5.6 の 1、p. 93)。

AB07 は同定理の 2($\mathrm P=\mathrm{NP}$ なら $\mathrm{PH}=\mathrm P$)だけを証明し、1 は同様として省いている。ここでは 1 を証明し、2 をその系として導く。要点は、先頭の $\exists u_1$ を固定した残りの条件が 1 段低いクラスの言語になり、仮定でその言語を量化子の向きが逆のクラスに移すと、隣り合った $\exists$ がまとまって段が 1 つ減ることである。

$\Sigma_k=\Pi_k$ とする。$j\ge k$ についての帰納法で $\Sigma_j=\Sigma_k$ と $\Pi_j=\Sigma_k$ を示す。$j=k$ では仮定そのものである。
$j\ge k$ で成り立つとし、$L\in\Sigma_{j+1}$ をとる。def-ph-def の $M,q$ により
$$ x\in L\iff\exists u_1\ \underbrace{\forall u_2\,\exists u_3\cdots Q_{j+1}u_{j+1}\ M(x,u_1,\dots,u_{j+1})=1}_{(\ast)} $$
と書ける。組 $\langle x,u_1\rangle$ で $\lvert u_1\rvert=q(\lvert x\rvert)$ かつ $(\ast)$ が成り立つものの言語を $L'$ とする。$L'$ は $\forall$ から始まる $j$ 個の量化子で書け、量化する列の長さ $q(\lvert x\rvert)$ は $\langle x,u_1\rangle$ の長さ以下である。$\langle x,u_1\rangle$ から $x$ を取り出して長さを確かめるのは多項式時間なので、長さが $q(\lvert x\rvert)$ でない列を lem-ph-basic の 3 の証明と同じく形の誤りとして扱えば、$L'\in\Pi_j$ である。
帰納法の仮定から $\Pi_j=\Sigma_k$ なので、$L'\in\Sigma_k$ である。よって多項式時間の $M'$ と多項式 $q'$ があって
$$ \langle x,u_1\rangle\in L'\iff\exists v_1\,\forall v_2\cdots Q_kv_k\ M'(\langle x,u_1\rangle,v_1,\dots,v_k)=1 $$
となる($v_i$ の長さは $q'(\lvert\langle x,u_1\rangle\rvert)$ で、これは $\lvert x\rvert$ の多項式でおさえられる)。したがって
$$ x\in L\iff\exists u_1\,\exists v_1\,\forall v_2\cdots Q_kv_k\ M'(\langle x,u_1\rangle,v_1,\dots,v_k)=1 $$
であり、$\exists u_1\,\exists v_1$ を 1 つの塊とみると、lem-ph-basic の 3 により $L\in\Sigma_k$ である。よって $\Sigma_{j+1}\subset\Sigma_k$ で、lem-ph-basic の 2 から $\Sigma_k\subset\Sigma_{j+1}$ なので $\Sigma_{j+1}=\Sigma_k$ である。lem-ph-basic の 1 と仮定から $\Pi_{j+1}=\mathrm{co}\Sigma_{j+1}=\mathrm{co}\Sigma_k=\Pi_k=\Sigma_k$ である。
以上ですべての $j\ge k$ で $\Sigma_j=\Sigma_k$ となり、$j< k$ の $\Sigma_j$ は lem-ph-basic の 2 で $\Sigma_k$ に含まれるので、$\mathrm{PH}=\Sigma_k$ である。$\square$

P = NP と NP = coNP の帰結
  1. $\mathrm{NP}=\mathrm{coNP}$ なら $\mathrm{PH}=\mathrm{NP}$ である。
  2. $\mathrm P=\mathrm{NP}$ なら $\mathrm{PH}=\mathrm P$ である(AB07 Theorem 5.6 の 2、p. 93)。

1 は thm-ph-collapse の $k=1$ である。2:$\mathrm P=\mathrm{NP}$ なら、$\mathrm P$ は補集合をとる操作で閉じているので $\mathrm{coNP}=\mathrm{coP}=\mathrm P=\mathrm{NP}$ であり、1 から $\mathrm{PH}=\mathrm{NP}=\mathrm P$ である。$\square$

対偶をとると、ある段で $\Sigma_k\ne\Sigma_{k+1}$ が示されれば $\mathrm P\ne\mathrm{NP}$ が従う。どの $k$ でも $\Sigma_k\ne\Sigma_{k+1}$ であるという予想を「多項式階層は潰れない」という。AB07(2007 年の版)の §5.2.1(p. 93)はこれを予想として述べ、計算量理論でしばしば仮定として使われるとしている。

各段の完全問題

量化した論理式の充足

$k\ge1$ とする。変数を $k$ 個の組 $u_1,\dots,u_k$ に分けた命題論理の論理式 $\varphi$(連言標準形とは限らない)で、
$$ \exists u_1\,\forall u_2\cdots Q_ku_k\ \ \varphi(u_1,\dots,u_k)=1 $$
が真になるものの全体を $\Sigma_k\mathrm{SAT}$ という。$\forall u_1$ から始めたものを $\Pi_k\mathrm{SAT}$ という(AB07 Example 5.9、p. 94)。

$\Sigma_1\mathrm{SAT}$ は(連言標準形に限らない)充足可能性問題である。

タブローの論理式

$M$ を多項式時間の決定的な算法、$r$ を多項式とする。$x$ から多項式時間で、変数 $u=(u^{(1)},\dots,u^{(r(\lvert x\rvert))})$ と補助の変数 $z$ をもつ連言標準形の論理式 $\varphi_x(u,z)$ を計算する算法があって、すべての $u\in\{0,1\}^{r(\lvert x\rvert)}$ について $M(x,u)=1\iff\exists z\ \varphi_x(u,z)=1$ となる。

補題の所在

これは Cook–Levinの定理 の証明の構成で、証明書にあたる $u$ のビットを固定せずに変数として残したものである。AB07 Lemma 2.12 の証明(§2.3.4、pp. 47–49)は、$M$ の入力 $y$(先頭が $x$、残りが $u$)と計算の各段の状態を表す $z$ を変数とする論理式を作っており、そのまま当てはまる。この記事では証明しない。

$\Sigma_k\mathrm{SAT}$ の完全性

$k\ge1$ について、$\Sigma_k\mathrm{SAT}$ は $\Sigma_k$ 完全である。すなわち $\Sigma_k\mathrm{SAT}\in\Sigma_k$ であり、$\Sigma_k$ のすべての言語は $\Sigma_k\mathrm{SAT}$ に多項式時間還元できる。同様に $\Pi_k\mathrm{SAT}$ は $\Pi_k$ 完全である。

証明を開く

所属:$u_i$ を割り当てとし、$M$ を「$\varphi$ を割り当てで評価する」算法とすれば、割り当ての長さは $\varphi$ の長さ以下なので lem-ph-basic の 3 により $\Sigma_k\mathrm{SAT}\in\Sigma_k$ である。

困難性:$L\in\Sigma_k$ を $M,q$ で表す。$k$ が奇数なら $Q_k=\exists$ である。lem-ph-tableau を $M$ と $r=kq$ に使い、$x\in L\iff\exists u_1\forall u_2\cdots\exists u_k\exists z\ \varphi_x(u_1,\dots,u_k,z)=1$ を得る。最後の 2 つの $\exists$ をまとめて組 $(u_k,z)$ とすれば、$x\mapsto\varphi_x$(変数を $k$ 個の組に分けたもの)は $L$ から $\Sigma_k\mathrm{SAT}$ への還元である。

$k$ が偶数なら $Q_k=\forall$ である。$\overline M:=1-M$ に lem-ph-tableau を使って $\psi_x$ を作ると、$M(x,u)=1\iff\overline M(x,u)=0\iff\neg\exists z\,\psi_x(u,z)\iff\forall z\,\neg\psi_x(u,z)$ である。よって $x\in L\iff\exists u_1\cdots\forall u_k\forall z\ \neg\psi_x=1$ で、最後の 2 つの $\forall$ をまとめれば $x\mapsto\neg\psi_x$ が還元である。$\neg\psi_x$ は連言標準形でないが、def-ph-sigmasat は任意の論理式を許す。

$\Pi_k\mathrm{SAT}$ は、$\Pi_k\mathrm{SAT}$ の補集合が「否定した式の $\Sigma_k\mathrm{SAT}$」であることと、lem-ph-basic の 1 から従う。$\square$

完全問題と崩壊

多項式時間還元について $\mathrm{PH}$ 完全な言語($\mathrm{PH}$ に属し、$\mathrm{PH}$ のすべての言語が還元できる言語)があれば、ある $k$ で $\mathrm{PH}=\Sigma_k$ である(AB07 Claim 5.7、p. 94)。

証明を開く

完全な言語 $L$ は $\mathrm{PH}=\bigcup_k\Sigma_k$ に属するので、ある $k$ で $L\in\Sigma_k$ である。$\mathrm{PH}$ の任意の言語は $L$ に還元でき、lem-ph-basic の 4 により $\Sigma_k$ に属する。$\square$

PSPACE との関係と神託による言い換え

PH は PSPACE に含まれる

$\mathrm{PH}\subset\mathrm{PSPACE}$ である(AB07 Remark 5.8、p. 94)。

証明を開く

$L\in\Sigma_k$ を $M,q$ で表し、$m:=q(\lvert x\rvert)$ とする。手続き $\mathrm{Eval}(i;u_1,\dots,u_{i-1})$ を、$i>k$ なら $M(x,u_1,\dots,u_k)$ を返し、$i\le k$ なら $u_i\in\{0,1\}^m$ を辞書式の順にすべて試して $\mathrm{Eval}(i+1;u_1,\dots,u_i)$ を計算し、$Q_i=\exists$ ならそれらの論理和、$\forall$ なら論理積を返すものとする。$\mathrm{Eval}(1;)$ が $x\in L$ の真偽である。再帰の深さは $k$ で、同時に覚えるのは $u_1,\dots,u_k$(合わせて $km$ ビット)と各段の途中の値、それに $M$ の計算の作業領域だけである。$M$ の作業領域はその時間以下で、多項式である。試した $u_i$ の領域は次の候補に使い回すので、全体の領域は $\lvert x\rvert$ の多項式である。$\square$

PH = PSPACE なら潰れる

$\mathrm{PH}=\mathrm{PSPACE}$ ならば、ある $k$ で $\mathrm{PH}=\Sigma_k$ である。

証明を開く

量化 Boolean 論理式の真偽の問題 TQBF は PSPACE完全である(PSPACE完全 の定理「TQBF の PSPACE完全性」)。$\mathrm{PH}=\mathrm{PSPACE}$ なら TQBF は $\mathrm{PH}$ 完全で、prop-ph-complete-collapse から結論が出る。$\square$

多項式階層は神託(オラクル)を使っても定義できる。言語 $O$ の 神託 をもつ算法とは、計算の途中で「列 $w$ は $O$ に属するか」を 1 ステップで問える算法である。神託 $O$ をもつ非決定的な多項式時間の算法で判定できる言語のクラスを $\mathrm{NP}^O$ と書く。

神託による特徴づけ

$i\ge2$ について $\Sigma_i=\mathrm{NP}^{\Sigma_{i-1}\mathrm{SAT}}$ である(AB07 Theorem 5.15、p. 98)。

AB07 は $i=2$ の場合($\Sigma_2=\mathrm{NP}^{\mathrm{SAT}}$)の証明で考え方を示している(pp. 98–99)。この記事では証明しない。完全問題の神託はそのクラス全体の神託と同じ力をもつので、$\Sigma_2$ を $\mathrm{NP}^{\mathrm{NP}}$、$\Sigma_3$ を $\mathrm{NP}^{\mathrm{NP}^{\mathrm{NP}}}$ と書く文献もある(AB07 Remark 5.16、p. 99)。決定的な算法に同じ神託を与えたクラス $\Delta_i:=\mathrm P^{\Sigma_{i-1}\mathrm{SAT}}$ は、$\Sigma_{i-1}$ と $\Pi_{i-1}$ を含み(神託に 1 回問えばよい)、$\mathrm{NP}^{\Sigma_{i-1}\mathrm{SAT}}=\Sigma_i$ に含まれ、補集合で閉じているので $\Pi_i$ にも含まれる。階層を細かく見るときに使う。
量化子の交代は、各状態に $\exists$ か $\forall$ の印を付けた 交代 Turing 機械 でも表せる。交代の回数を制限しない多項式時間の交代 Turing 機械のクラスは $\mathrm{PSPACE}$ に一致する(AB07 Theorem 5.12、p. 96)。

公式の表

主張条件根拠
$\Sigma_1=\mathrm{NP}$、$\Pi_1=\mathrm{coNP}$、$\Sigma_0=\Pi_0=\mathrm P$—def-ph-def
$\Pi_k=\mathrm{co}\Sigma_k$—lem-ph-basic
$\Sigma_k\cup\Pi_k\subset\Sigma_{k+1}\cap\Pi_{k+1}$—lem-ph-basic
$\Sigma_k=\Pi_k\Rightarrow\mathrm{PH}=\Sigma_k$$k\ge1$thm-ph-collapse
$\mathrm P=\mathrm{NP}\Rightarrow\mathrm{PH}=\mathrm P$—cor-ph-pnp
$\Sigma_k\mathrm{SAT}$ は $\Sigma_k$ 完全$k\ge1$thm-ph-complete
PH 完全な言語がある $\Rightarrow$ 潰れる多項式時間還元prop-ph-complete-collapse
$\mathrm{PH}\subset\mathrm{PSPACE}$—prop-ph-pspace
$\mathrm{PH}=\mathrm{PSPACE}\Rightarrow$ 潰れる—cor-ph-pspace
$\Sigma_i=\mathrm{NP}^{\Sigma_{i-1}\mathrm{SAT}}$$i\ge2$証明しない(AB07 Theorem 5.15)
$\mathrm{NP}\subset\mathrm{P/poly}\Rightarrow\mathrm{PH}=\Sigma_2$—回路計算量(Karp–Lipton の定理)
$\mathrm{PH}\subset\mathrm P^{\#\mathrm P}$—戸田の定理(計算量)

計算の手順

言語がどの段に入るかを調べる手順:

  1. 条件を量化子で書く:「$x\in L$」を、多項式時間で確かめられる条件の前に $\exists,\forall$ を並べた形に書き直す。
  2. 長さを確かめる:量化する対象(集合・割り当て・論理式など)を列で表し、長さが $\lvert x\rvert$ の多項式でおさえられることを確かめる。
  3. 塊を数える:同じ量化子が続く箇所を 1 つにまとめ(lem-ph-basic の 3)、$\exists$ から始まる $k$ 個の塊なら $\Sigma_k$、$\forall$ から始まるなら $\Pi_k$ である。
  4. 完全性を示す:下界を示すには、$\Sigma_k\mathrm{SAT}$ などの完全問題から多項式時間で還元する(thm-ph-complete)。

例題

最大の独立集合の大きさ

使う公式:手順の 1〜3。
問:「$G$ の独立集合の最大の大きさがちょうど $k$」という言語 EXACT INDSET が $\Sigma_2$ に属することを示し、道 $1-2-3-4$(辺 $\{1,2\},\{2,3\},\{3,4\}$)と $k=2$ で確かめよ。
答え:$\langle G,k\rangle\in L\iff\exists S\,\forall T$($S$ は大きさ $k$ の独立集合で、$T$ は大きさ $k+1$ の独立集合でない)と書ける。独立集合の部分集合は独立集合なので、大きさ $k+1$ のものがなければ $k+1$ 以上のものもない。部分集合は頂点数のビット列で表せ、括弧の中は多項式時間で確かめられるので $\Sigma_2$ である(AB07 Example 5.2、p. 92)。道では大きさ 2 の独立集合は $\{1,3\},\{1,4\},\{2,4\}$ の 3 つで、大きさ 3 のものはない。$S=\{1,3\}$ が証拠で、4 ビットの $S,T$ を総当たりすると内側の判定は $16\times16=256$ 回である。「すべての大きさ $k+1$ の $T$ は独立でなく、大きさ $k$ の独立な $S$ がある」とも書けるので、$\Pi_2$ にも属する(同 Example 5.3)。

量化子の順序

使う公式:def-ph-sigmasat。
問:1 ビットの変数 $x,y$ について、$\exists x\,\forall y\ (x\vee y)\wedge(x\vee\neg y)$、$\forall y\,\exists x\ (x\leftrightarrow y)$、$\exists x\,\forall y\ (x\leftrightarrow y)$ の真偽を求めよ。
答え:1 つ目は $x=1$ で真で、$\Sigma_2\mathrm{SAT}$ に属する。2 つ目は $x:=y$ とすれば真で、$\Pi_2\mathrm{SAT}$ に属する。3 つ目はどの $x$ についても $y=1-x$ で偽になる。同じ論理式でも量化子の順序を入れ替えると真偽が変わる。

最小の論理式

使う公式:手順の 1〜3。
問:加法標準形(DNF)の論理式で、リテラルの個数が少ない同値な DNF がないものの言語 MIN-DNF が $\Pi_2$ に属することを示し、$x_1\vee(x_1\wedge x_2)$ と $x_1\vee x_2$ を判定せよ。
答え:$\varphi\in L\iff\forall\psi\,\exists s$($\psi$ が $\varphi$ よりリテラルが少ないなら $\psi(s)\ne\varphi(s)$)と書けるので $\Pi_2$ である(AB07 p. 92。$\Pi_2$ 完全であると予想されている)。$x_1\vee(x_1\wedge x_2)$(リテラル 3 個)は $x_1$(1 個)と同値なので属さない。$x_1\vee x_2$(2 個)は、リテラル 1 個以下の DNF(恒偽、恒真、$x_1,\neg x_1,x_2,\neg x_2$)のどれとも真理値表が異なるので属する。

総当たりの手間

使う公式:prop-ph-pspace の証明。
問:$\Sigma_2$ の式で $u_1,u_2$ がそれぞれ $m$ ビットのとき、prop-ph-pspace の手続きで $M$ を何回呼ぶか。$m=30$ ではどうか。
答え:$2^m\cdot2^m=2^{2m}$ 回で、$m=30$ なら $2^{60}\approx1.152922\times10^{18}$ 回である。時間は指数的だが、同時に覚える列は $2m=60$ ビットと $M$ の作業領域だけである。

使える条件と反例

外す条件反例成り立たなくなること
(i) $M$ が多項式時間$M$ に指数時間を許すと、量化子なしの段 $\Sigma_0$ が EXP を含む$\mathrm P\ne\mathrm{EXP}$(計算量理論)なので $\Sigma_0=\mathrm P$ が成り立たない
(iii) 塊の個数が定数塊の個数を入力の長さとともに増やすと、量化 Boolean 論理式の真偽 TQBF が表せ、クラスは PSPACE になる(交代 Turing 機械で述べた形が AB07 Theorem 5.12)prop-ph-complete-collapse の論法(完全問題がどこかの段に入る)が使えない。TQBF がある段に入ると示されたわけではなく、入れば $\mathrm{PH}$ が潰れる(cor-ph-pspace)
(iv) 還元が多項式時間指数時間の還元を許すと、$\mathrm{PH}$ の $L$ は $x\in L$ なら $1$、そうでなければ $0$ を返す写像で $\{1\}$ に還元される(prop-ph-pspace から $L$ は指数時間で判定できる)$\{1\}\in\mathrm P$ が「PH 完全」になり、prop-ph-complete-collapse の結論 $\mathrm{PH}=\Sigma_0$ は導けない(lem-ph-basic の 4 が使えない)

よくある誤り

誤り正しくはなぜ
$\mathrm{PH}=\mathrm{PSPACE}$ である分かっていない。等しければ階層は潰れるcor-ph-pspace
量化子の順序は入れ替えてよい$\exists\forall$ と $\forall\exists$ で真偽が変わるex-ph-order
量化する変数の個数が段の数同じ量化子の連続は 1 つの塊と数えるlem-ph-basic の 3
$\Sigma_k\cap\Pi_k=\Sigma_{k-1}\cup\Pi_{k-1}$一致するとは分かっていない。EXACT INDSET は $\Sigma_2\cap\Pi_2$ に入るが、所属を示す短い証明書は見当たらないex-ph-exactindset、AB07 p. 91
$\Sigma_{k+1}\ne\Sigma_k$ は証明されている予想である。示されれば $\mathrm P\ne\mathrm{NP}$ が従うcor-ph-pnp
$\mathrm{NP}^{\mathrm{NP}}$ の神託は NP の任意の言語完全問題 SAT の神託と同じ力なので、どちらでもクラスは同じAB07 Remark 5.16

補足

多項式階層は Stockmeyer が 1977 年の論文で形式的に定義した。それ以前にも Karp(1972 年)が、Kleene の算術的階層の多項式版は $\mathrm P=\mathrm{NP}$ なら自明になると注意している(AB07 第 5 章の文献の注、p. 99)。計算量理論では、「階層は潰れない」を仮定して他の主張の確からしさを測ることが多い。回路計算量 の Karp–Lipton の定理は、$\mathrm{NP}$ の言語がすべて多項式の大きさの回路の族をもてば $\mathrm{PH}=\Sigma_2$ となることを示すので、階層が潰れないと信じる限り SAT は多項式の大きさの回路をもたない。戸田の定理(計算量) は、$\mathrm{PH}$ 全体が数え上げの神託を 1 回使う多項式時間の算法に含まれることを示す。
量化子の交代で階層を作る考え方は、計算可能性の理論で、計算可能な述語の前に自然数の量化子を並べた 算術的階層 と同じ形をしている。多項式階層は、量化する対象を長さが多項式の列に、述語を多項式時間のものに制限したものである。有界算術 の理論は、多項式階層の段と証明できる関数を対応させる。

関連項目

参考文献

[1]
Sanjeev Arora; Boaz Barak, Computational Complexity: A Modern Approach, Web draft(2007-01-08)。刊行版は 2009 年, Cambridge University Press, 2009, 頁は Web draft 2007-01-08 の通し頁:§2.3.4 Lemma 2.12 の証明 pp. 47–49、§5.1(Examples 5.2–5.3)pp. 91–92、Definition 5.4 と Theorem 5.6 と §5.2.1 p. 93、Claim 5.7・Remark 5.8・Example 5.9 p. 94、Theorem 5.12 p. 96、Theorem 5.15 と Remark 5.16 pp. 98–99、第 5 章の文献の注 p. 99

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する