多項式階層

多項式階層（たこうしきかいそう、）は、計算量理論における計算量の階層であり、神託機械を使って P、NP、co-NP を一般化させて定義されるものである。
定義.
多項式階層をなすクラス群の定義はいくつか存在する。
</math>
formula_1
ここで、AB はクラス A のチューリングマシンにクラス B の何らかの問題を解く神託を付加して強化したもので解ける決定問題の集合である。例えば、formula_2 であり、formula_3 は NP に属する何らかの問題を解く神託を備えることで多項式時間で解ける問題のクラスである。
多項式階層の存在/全称的定義のため、formula_4 を形式言語（すなわち、一種の決定問題であり、{0,1}* の部分集合である）、formula_5 を多項式とし、次のように定義する。
ここで、formula_6 は2進文字列 "x" と "w" を1つの2進文字列にする何らかの標準的符号化である。"L" は文字列の順序対の集合を表しており、第一の文字列 "x" は formula_7 の元で、第二の文字列 "w" は "x" が formula_7 の元であることを示す短い (formula_9) 証拠である。言い換えれば、formula_10 は、formula_11 であるような短い証拠 "w" が存在することと同値である。同様に次のように定義する。
ドモルガンの定理により、formula_12 かつ formula_13 であり、ここで "L"c は "L" の補集合である。ここで formula_14 を言語のクラスとする。次のように定義することで、これら作用素が言語のクラス群全体に作用するよう拡張する。
再びドモルガンの定理により、formula_15 かつ formula_16 であり、ここで formula_17 である。クラス NP と co-NP は formula_18 と formula_19 と定義され、ここで P は（多項式時間で）適切に決定可能な言語群の全体のクラスである。多項式階層は次のように再帰的に定義できる。
なお、formula_20 であり、かつ formula_21 である。この定義は多項式階層と算術的階層の密接な関連を反映しており、後者で DEC と CE が果たした役割をそれぞれ P と NP が果たしている。同様の方法で、実数の部分集合の階層として解析的階層が定義される。
交替性チューリング機械を使った等価な定義として、formula_22（あるいは formula_23）は存在的状態（あるいは全称的状態）から開始する交替性チューリング機械で formula_24 回の交替を行うことで多項式時間で解ける決定問題の集合と定義される。
多項式階層内のクラス間の関係.
定義から、次のような関係が成り立つ。
真の包含であることがわかっている算術的階層や解析的階層とは異なり、これらの包含関係が厳密かどうか（真部分集合かどうか）は未解決の問題である。ただし、これら全てが厳密な包含関係であると広く信じられている。もしこれが成り立たず、ある "k" について formula_25 すなわち formula_26 となることを「多項式階層が第 "k" 層で潰れる」と言う。もしそうなら全ての formula_27 について formula_28 となる。特に P = NP なら、階層は完全に潰れる。
多項式階層にある全クラス群の和集合を PH と書く。
多項式時間階層は、指数時間階層や算術的階層に似ている。
PH が PSPACE に包含されることは知られているが、2つのクラスが等しいかどうかは不明である。この問題を言い換えると、PH = PSPACE であるならば、二階述語論理に推移閉包演算子を追加しても強化されないことになる。
もし多項式階層が完全問題を含むなら、どこかの層に潰れる。PSPACE完全問題は存在するので、PSPACE = PH ならば、PSPACE完全問題がformula_29-完全問題だということになるので、多項式階層は潰れる。
多項式階層の各層については formula_30-完全問題（多項式時間多対一還元において完全な問題）がある。さらに、多項式階層の各層は formula_30-還元において閉じている。つまり、この階層上のあるクラス formula_14 と言語 formula_33 があるとき、formula_34 ならば、同時に formula_35 である。これらの事実から、formula_36 を formula_37 の完全問題としたとき、formula_38 と formula_39 が成り立つことがわかる。実際、formula_40 である。言い換えれば、言語を formula_14 に含まれる何らかの神託機械に基づいて定義したとき、それを formula_14 の完全問題に基づいて定義したと見なすことができる。完全問題は従って、それが完全であるとするクラスを代表していると見なせる。