PH (計算複雑性理論)

計算複雑性理論における複雑性クラス PH とは、多項式階層にある全ての複雑性クラスの和集合である。次のように表される。

[math]\mbox{PH} = \bigcup_{k\in\mathbb{N}} \Delta_k^{\rm{P}}[/math]

PH は Larry Stockmeyer が最初に定義した。これを包含するクラスとして、P^PP（PPをオラクルとして持つ神託機械で多項式時間で解ける問題のクラス）、P^#P（戸田の定理による）、PSPACE がある。

PH の論理的な特徴付けはごく単純。つまり、二階述語論理で可能な全ての言明の集合である。

PH は PSPACE に含まれる既知の複雑性クラスのほとんどを包含している。特に P、NP、co-NP が含まれる。また、確率的なクラスである BPP や RP も包含している。

P = NP の必要十分条件は P = PH であることである。つまり、より一般的なクラス PH から P を分離できさえすればよいので、P ≠ NP の証明の単純化に繋がるかも知れない（P≠NP予想）。

参考文献

• L. J. Stockmeyer, "The polynomial hierarchy", Theoretical Computer Science, Vol. 3 (1976), pp. 1–22.
• The Complexity Zoo: PH

脚注

テンプレート:複雑性クラス