PH (計算複雑性理論)

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

${\displaystyle {\mbox{PH}}=\bigcup _{k\in \mathbb {N} }\Delta _{k}^{\rm {P}}}$

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

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

• 表示
• 編集

表 話 編 歴 主な複雑性クラス
実用的な時間で解けるクラス	DLOGTIME AC0 ACC0 TC0 L SL RL NL NC SC CC P P完全 ZPP RP BPP BQP APX
実用的な時間で解けないと疑われているクラス	UP NP NP完全 NP困難 co-NP co-NP完全 AM QMA PH ⊕P PP #P #P完全 IP PSPACE
実用的な時間では解けないクラス	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL
クラス階層	多項式階層 指数階層 グジェゴルチク階層 算術的階層 ブーリアン階層
クラスの族	DTIME NTIME DSPACE NSPACE PCP 対話型証明系
一覧・ カテゴリ