Statements (54)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
theoretical computer science
|
| gptkbp:abbreviation |
polynomial hierarchy
|
| gptkbp:contains |
gptkb:co-NP
P NP Π_k^P (Pi_k^P) Σ_k^P (Sigma_k^P) |
| gptkbp:definedIn |
alternating quantifiers over polynomial-time predicates
|
| gptkbp:equivalentTo |
PH
|
| gptkbp:field |
theoretical computer science
|
| gptkbp:generalizes |
gptkb:co-NP
NP |
| gptkbp:hasSubgroup |
gptkb:BQP
gptkb:BPP gptkb:EXPTIME gptkb:PSPACE gptkb:co-NP gptkb:ZPP P NP RP P^#P |
| https://www.w3.org/2000/01/rdf-schema#label |
PH (polynomial hierarchy)
|
| gptkbp:introduced |
gptkb:Larry_Stockmeyer
|
| gptkbp:introducedIn |
1976
|
| gptkbp:isHierarchy |
based on quantifier alternation
between P and PSPACE |
| gptkbp:isLevel |
Π_k^P (Pi_k^P)
Σ_k^P (Sigma_k^P) |
| gptkbp:isOpenQuestion |
whether PH = NP
whether PH = P whether PH = PSPACE whether PH = co-NP whether PH collapses whether PH is infinite |
| gptkbp:isUnionOf |
Π_k^P (Pi_k^P) for all k
Σ_k^P (Sigma_k^P) for all k |
| gptkbp:relatedTo |
gptkb:arithmetical_hierarchy
gptkb:Karp-Lipton_theorem gptkb:Boolean_hierarchy gptkb:P/poly #P oracle machines randomized complexity classes PH-complete problems Toda's theorem collapse of the hierarchy complete problems for levels of PH polynomial-time hierarchy quantum complexity classes relativization |
| gptkbp:bfsParent |
gptkb:NP_(complexity_class)
gptkb:P_(complexity_class) |
| gptkbp:bfsLayer |
6
|