多項式階層

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

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


\Pi_{i+1}^{\rm P} := \mbox{coNP}^{\Sigma_i^{\rm P}}
}}
ここで、AB はクラス A のチューリングマシンにクラス B の何らかの問題を解く神託を付加して強化したもので解ける決定問題の集合である。例えば、 \Sigma_1^{\rm P} = {\rm NP}, \Pi_1^{\rm P} = {\rm coNP}  であり、 \Delta_2^{\rm P} = {\rm P^{NP}}  は **NP** に属する何らかの問題を解く神託を備えることで多項式時間で解ける問題のクラスである。
|
多項式階層の存在/全称的定義のため、L を形式言語（すなわち、一種の決定問題であり、{0,1}* の部分集合である）、p を多項式とし、次のように定義する。

ここで、\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* が存在することと同値である。同様に次のように定義する。

ドモルガンの定理により、 \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} を言語のクラスとする。次のように定義することで、これら作用素が言語のクラス群全体に作用するよう拡張する。

再びドモルガンの定理により、 {\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 (計算複雑性理論)|P]]** は（多項式時間で）適切に決定可能な言語群の全体のクラスである。多項式階層は次のように再帰的に定義できる。

なお、 {\rm NP} = \Sigma_1^{\rm P}  であり、かつ  {\rm coNP} = \Pi_1^{\rm P}  である。この定義は多項式階層と算術的階層の密接な関連を反映しており、後者で **[[帰納言語|DEC]]** と **[[帰納的可算言語|CE]]** が果たした役割をそれぞれ **[[P (計算量理論)|P]]** と **[[NP]]** が果たしている。同様の方法で、実数の部分集合の階層として解析的階層が定義される。
|
交替性チューリング機械を使った等価な定義として、\Sigma_k^{\rm P}（あるいは \Pi_k^{\rm P}）は存在的状態（あるいは全称的状態）から開始する交替性チューリング機械で k 回の交替を行うことで多項式時間で解ける決定問題の集合と定義される。
}}

## 多項式階層内のクラス間の関係
定義から、次のような関係が成り立つ。

真の包含であることがわかっている算術的階層や解析的階層とは異なり、これらの包含関係が厳密かどうか（真部分集合かどうか）は未解決の問題である。ただし、これら全てが厳密な包含関係であると広く信じられている。もしこれが成り立たず、ある *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]]** と書く。

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

**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} の完全問題に基づいて定義したと見なすことができる。完全問題は従って、それが完全であるとするクラスを代表していると見なせる。

## 多項式階層内の問題

## 参考文献
* 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&ndash;129, 1972.  多項式階層を提唱した論文。
* L. J. Stockmeyer. [The polynomial-time hierarchy](https://doi.org/10.1016/0304-3975(76)90061-X). *Theoretical Computer Science*, vol.3, pp.1&ndash;22, 1976.
* C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Chapter 17. *Polynomial hierarchy*, pp. 409&ndash;438.
*  Section 7.2: The Polynomial Hierarchy, pp.161&ndash;167.