多項式階層（たこうしきかいそう、）は、計算量理論における計算量の階層であり、神託機械を使って P、NP、co-NP を一般化させて定義されるものである。多項式階層をなすクラス群の定義はいくつか存在する。定義から、次のような関係が成り立つ。真の包含であることがわかっている算術的階層や解析的階層とは異なり、これらの包含関係が厳密かどうか（真部分集合かどうか）は未解決の問題である。ただし、これら全てが厳密な包含関係であると広く信じられている。もしこれが成り立たず、ある "k" について formula_1 すなわち formula_2 となることを「多項式階層が第 "k" 層で潰れる」と言う。もしそうなら全ての formula_3 について formula_4 となる。特に P = NP なら、階層は完全に潰れる。多項式階層にある全クラス群の和集合を PH と書く。多項式時間階層は、指数時間階層や算術的階層に似ている。PH が PSPACE に包含されることは知られているが、2つのクラスが等しいかどうかは不明である。この問題を言い換えると、PH = PSPACE であるならば、二階述語論理に推移閉包演算子を追加しても強化されないことになる。もし多項式階層が完全問題を含むなら、どこかの層に潰れる。PSPACE完全問題は存在するので、PSPACE = PH ならば、PSPACE完全問題がformula_5-完全問題だということになるので、多項式階層は潰れる。多項式階層の各層については formula_6-完全問題（多項式時間多対一還元において完全な問題）がある。さらに、多項式階層の各層は formula_6-還元において閉じている。つまり、この階層上のあるクラス formula_8 と言語 formula_9 があるとき、formula_10 ならば、同時に formula_11 である。これらの事実から、formula_12 を formula_13 の完全問題としたとき、formula_14 と formula_15 が成り立つことがわかる。実際、formula_16 である。言い換えれば、言語を formula_8 に含まれる何らかの神託機械に基づいて定義したとき、それを formula_8 の完全問題に基づいて定義したと見なすことができる。完全問題は従って、それが完全であるとするクラスを代表していると見なせる。

出典:wikipedia