多項式階層

多項式階層（たこうしきかいそう、英: Polynomial hierarchy）は、計算量理論における計算量の階層であり、神託機械を使って P、NP、co-NP を一般化させて定義されるものである。

定義

多項式階層をなすクラス群の定義はいくつか存在する。

1. 多項式階層は神託機械を使って次のように定義する。

   $\Delta _{0}^{\rm {P}}:=\Sigma _{0}^{\rm {P}}:=\Pi _{0}^{\rm {P}}:={\mbox{P}},$

   ここで、P は多項式時間内で解ける決定問題の集合である。i ≥ 0 については、次のように定義する。

   $\Delta _{i+1}^{\rm {P}}:={\mbox{P}}^{\Sigma _{i}^{\rm {P}}}$
   $\Sigma _{i+1}^{\rm {P}}:={\mbox{NP}}^{\Sigma _{i}^{\rm {P}}}$
   $\Pi _{i+1}^{\rm {P}}:={\mbox{coNP}}^{\Sigma _{i}^{\rm {P}}}$

   ここで、A^B はクラス A のチューリングマシンにクラス B の何らかの問題を解く神託を付加して強化したもので解ける決定問題の集合である。例えば、$\Sigma _{1}^{\rm {P}}={\rm {NP}},\Pi _{1}^{\rm {P}}={\rm {coNP}}$ であり、$\Delta _{2}^{\rm {P}}={\rm {P^{NP}}}$ は NP に属する何らかの問題を解く神託を備えることで多項式時間で解ける問題のクラスである。

2. 多項式階層の存在/全称的定義のため、$L$ を形式言語（すなわち、一種の決定問題であり、{0,1}^* の部分集合である）、$p$ を多項式とし、次のように定義する。

   $\exists ^{p}L:=\left\{x\in \{0,1\}^{*}\ \left|\ \left(\exists w\in \{0,1\}^{\leq p(|x|)}\right)\langle x,w\rangle \in L\right.\right\},$

   ここで、$\langle x,w\rangle \in \{0,1\}^{*}$ は2進文字列 x と w を1つの2進文字列にする何らかの標準的符号化である。L は文字列の順序対の集合を表しており、第一の文字列 x は $\exists ^{p}L$ の元で、第二の文字列 w は x が $\exists ^{p}L$ の元であることを示す短い ($|w|\leq p(|x|)$) 証拠である。言い換えれば、$x\in \exists ^{p}L$ は、$\langle x,w\rangle \in L$ であるような短い証拠 w が存在することと同値である。同様に次のように定義する。

   $\forall ^{p}L:=\left\{x\in \{0,1\}^{*}\ \left|\ \left(\forall w\in \{0,1\}^{\leq p(|x|)}\right)\langle x,w\rangle \in L\right.\right\}$

   ドモルガンの定理により、$\left(\exists ^{p}L\right)^{\rm {c}}=\forall ^{p}L^{\rm {c}}$ かつ $\left(\forall ^{p}L\right)^{\rm {c}}=\exists ^{p}L^{\rm {c}}$ であり、ここで L^c は L の補集合である。ここで ${\mathcal {C}}$ を言語のクラスとする。次のように定義することで、これら作用素が言語のクラス群全体に作用するよう拡張する。

   $\exists ^{\rm {P}}{\mathcal {C}}:=\left\{\exists ^{p}L\ |\ p{\mbox{ is a polynomial and }}L\in {\mathcal {C}}\right\}$
   $\forall ^{\rm {P}}{\mathcal {C}}:=\left\{\forall ^{p}L\ |\ p{\mbox{ is a polynomial and }}L\in {\mathcal {C}}\right\}$

   再びドモルガンの定理により、${\rm {co}}\exists ^{\rm {P}}{\mathcal {C}}=\forall ^{\rm {P}}{\rm {co}}{\mathcal {C}}$ かつ ${\rm {co}}\forall ^{\rm {P}}{\mathcal {C}}=\exists ^{\rm {P}}{\rm {co}}{\mathcal {C}}$ であり、ここで ${\rm {co}}{\mathcal {C}}=\left\{L^{c}|L\in {\mathcal {C}}\right\}$ である。クラス NP と co-NP は ${\rm {NP}}=\exists ^{\rm {P}}{\rm {P}}$ と ${\rm {coNP}}=\forall ^{\rm {P}}{\rm {P}}$ と定義され、ここで P は（多項式時間で）適切に決定可能な言語群の全体のクラスである。多項式階層は次のように再帰的に定義できる。

   $\Sigma _{0}^{\rm {P}}:=\Pi _{0}^{\rm {P}}:={\rm {P}}$

   $\Sigma _{k+1}^{\rm {P}}:=\exists ^{\rm {P}}\Pi _{k}^{\rm {P}}$

   $\Pi _{k+1}^{\rm {P}}:=\forall ^{\rm {P}}\Sigma _{k}^{\rm {P}}$

   なお、${\rm {NP}}=\Sigma _{1}^{\rm {P}}$ であり、かつ ${\rm {coNP}}=\Pi _{1}^{\rm {P}}$ である。この定義は多項式階層と算術的階層の密接な関連を反映しており、後者で DEC と CE が果たした役割をそれぞれ P と NP が果たしている。同様の方法で、実数の部分集合の階層として解析的階層が定義される。

3. 交替性チューリング機械を使った等価な定義として、$\Sigma _{k}^{\rm {P}}$（あるいは $\Pi _{k}^{\rm {P}}$）は存在的状態（あるいは全称的状態）から開始する交替性チューリング機械で $k$ 回の交替を行うことで多項式時間で解ける決定問題の集合と定義される。

多項式階層内のクラス間の関係

定義から、次のような関係が成り立つ。

$\Sigma _{i}^{\rm {P}}\subseteq \Delta _{i+1}^{\rm {P}}\subseteq \Sigma _{i+1}^{\rm {P}}$
$\Pi _{i}^{\rm {P}}\subseteq \Delta _{i+1}^{\rm {P}}\subseteq \Pi _{i+1}^{\rm {P}}$
$\Sigma _{i}^{\rm {P}}={\rm {co}}\Pi _{i}^{\rm {P}}$

真の包含であることがわかっている算術的階層や解析的階層とは異なり、これらの包含関係が厳密かどうか（真部分集合かどうか）は未解決の問題である。ただし、これら全てが厳密な包含関係であると広く信じられている。もしこれが成り立たず、ある k について $\Sigma _{k}^{\rm {P}}=\Sigma _{k+1}^{\rm {P}}$ すなわち $\Sigma _{k}^{\rm {P}}=\Pi _{k}^{\rm {P}}$ となることを「多項式階層が第 k 層で潰れる」と言う。もしそうなら全ての $i>k$ について $\Sigma _{i}^{\rm {P}}=\Sigma _{k}^{\rm {P}}$ となる。特に P = NP なら、階層は完全に潰れる。

多項式階層にある全クラス群の和集合を PH と書く。

多項式時間階層は、指数時間階層や算術的階層に似ている。

PH が PSPACE に包含されることは知られているが、2つのクラスが等しいかどうかは不明である。この問題を言い換えると、PH = PSPACE であるならば、二階述語論理に推移閉包演算子を追加しても強化されないことになる。

もし多項式階層が完全問題を含むなら、どこかの層に潰れる。PSPACE完全問題は存在するので、PSPACE = PH ならば、PSPACE完全問題が$\Sigma _{k}^{\rm {P}}$-完全問題だということになるので、多項式階層は潰れる。

多項式階層の各層については $\leq _{\rm {m}}^{\rm {P}}$-完全問題（多項式時間多対一還元において完全な問題）がある。さらに、多項式階層の各層は $\leq _{\rm {m}}^{\rm {P}}$-還元において閉じている。つまり、この階層上のあるクラス ${\mathcal {C}}$ と言語 $L\in {\mathcal {C}}$ があるとき、$A\leq _{\rm {m}}^{\rm {P}}L$ ならば、同時に $A\in {\mathcal {C}}$ である。これらの事実から、$K_{i}$ を $\Sigma _{i}^{\rm {P}}$ の完全問題としたとき、$\Sigma _{i+1}^{\rm {P}}=\left(\Sigma _{i}^{\rm {P}}\right)^{K_{i}}$ と $\Pi _{i+1}^{\rm {P}}=\left(\Pi _{i}^{\rm {P}}\right)^{K_{i}^{\rm {c}}}$ が成り立つことがわかる。実際、$\Sigma _{2}^{\rm {P}}={\rm {NP}}^{\rm {SAT}}$ である。言い換えれば、言語を ${\mathcal {C}}$ に含まれる何らかの神託機械に基づいて定義したとき、それを ${\mathcal {C}}$ の完全問題に基づいて定義したと見なすことができる。完全問題は従って、それが完全であるとするクラスを代表していると見なせる。

多項式階層内の問題

• $\Sigma _{2}^{P}$ に属する問題の具体例として「回路最小化」問題がある。ある数 k とブール関数 f を計算する回路 A があるとき、同じ関数 f を最大 k 個の論理ゲートで計算できる回路が存在するかを問う決定問題である。${\mathcal {C}}$ を全ての論理回路の集合とする。この場合の言語 L は次のように定義される。

  $L=\left\{\langle A,k,B,x\rangle \in {\mathcal {C}}\times \mathbb {N} \times {\mathcal {C}}\times \{0,1\}^{*}\left|B{\mbox{ has at most }}k{\mbox{ gates, and }}A(x)=B(x)\right.\right\}$

  これは多項式時間で決定可能である。次の言語 CM が回路最小化問題を表す言語である。

  $CM=\left\{\langle A,k\rangle \in {\mathcal {C}}\times \mathbb {N} \left|{\begin{matrix}{\mbox{there exists a circuit }}B{\mbox{ with at most }}k{\mbox{ gates }}\\{\mbox{ such that }}A{\mbox{ and }}B{\mbox{ compute the same function}}\end{matrix}}\right.\right\}$

  $L$ が多項式時間で決定可能であり、かつ与えられた $\langle A,k\rangle$ について $\langle A,k\rangle \in CM$ であることと全ての入力 $x$ について $\langle A,k,B,x\rangle \in L$ となる回路 $B$ が存在することは同値であることから、$CM\in \Sigma _{2}^{P}(=\exists ^{\rm {P}}\forall ^{\rm {P}}{\rm {P}})$ が成り立つ。

• $\Sigma _{k}^{\rm {P}}$ の完全問題として k回の量化子交替のある「限量記号付きブール式問題」（QBF_k または QSAT_k と略記される）がある。これは充足可能性問題を $\Sigma _{k}^{\rm {P}}$ 向けにしたものである。この問題では、与えられるブール論理式 f の変数は k 個の集合 X₁, ..., X_k に分けられる。ここで次が真かどうかを決定しなくてはならない。

  $\exists X_{1}\forall X_{2}\exists X_{3}\ldots f$

  すなわち、X₁ に f を満足する値の組合せがあり、かつ X₂ の値の全ての組合せが f を満足し、かつ X₃ に f を満足する値の組合せがあり、… という組合せが存在するかどうか、という問題である。この順序の問題は $\Sigma _{k}^{\rm {P}}$ について完全である。全称記号が最初にあって、次が存在記号という順序になっている問題は $\Pi _{k}^{\rm {P}}$ について完全である。

参考文献

• A. R. Meyer and L. J. Stockmeyer. The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space. In Proceedings of the 13th IEEE Symposium on Switching and Automata Theory, pp. 125–129, 1972. 多項式階層を提唱した論文。
• L. J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, vol.3, pp.1–22, 1976.
• C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Chapter 17. Polynomial hierarchy, pp. 409–438.
• Michael R. Garey and David S. Johnson (1979年). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5  Section 7.2: The Polynomial Hierarchy, pp.161–167.