多項式階層

テンプレート:No footnotes 多項式階層（たこうしきかいそう、テンプレート:Lang-en-short）は、計算量理論における計算量の階層であり、神託機械を使って P、NP、co-NP を一般化させて定義されるものである。

定義

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

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

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

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

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

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

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

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

参考文献

• 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.
• テンプレート:Cite book Section 7.2: The Polynomial Hierarchy, pp.161–167.