Also known as Polynomial Hierarchy
algorithmic complexity class; the union of all complexity classes in the polynomial hierarchy; the set of languages expressible by second-order logic
Wikidata facts
- Instance of
- complexity class
- Subclass of
- computational problem
- Part of
- PSPACE
- Named after
- polynomial hierarchy
Show 1 more fact
- maintained by WikiProject
- WikiProject Mathematics
Sources (3)
via Wikidata · CC0
Article · 日本語
計算複雑性理論における複雑性クラス PH とは、多項式階層にある全ての複雑性クラスの和集合である。次のように表される。 PH は Larry Stockmeyer が最初に定義した。これを包含するクラスとして、PPP（PPをオラクルとして持つ神託機械で多項式時間で解ける問題のクラス）、P#P（戸田の定理による）、PSPACE がある。 PH の論理的な特徴付けはごく単純。つまり、二階述語論理で可能な全ての言明の集合である。 PH は PSPACE に含まれる既知の複雑性クラスのほとんどを包含している。特に P、NP、co-NP が含まれる。また、確率的なクラスである BPP や RP も包含している。 P = NP の必要十分条件は P = PH であることである。つまり、より一般的なクラス PH から P を分離できさえすればよいので、P ≠ NP の証明の単純化に繋がるかも知れない（P≠NP予想）。
Abstract from DBpedia / Wikipedia · CC BY-SA