PH (complexity)
|
|
In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy:
- <math>\mbox{PH} = \bigcup_{k\in\mathbb{N}} \Delta_k\mbox{P}<math>
PH is contained in the complexity classes PPP (the class of problems that are decidable by a polynomial time Turing machine with an access to PP oracle) and PSPACE.
PH has a simple logical characterization: it is the set of languages expressible by second order logic.
PH contains almost all well-known complexity classes inside PSPACE; in particular, it contains P, NP, and co-NP. It even contains probabilistic classes such as BPP and RP.
If P = NP, then P = PH.
| Important complexity classes (more) |
| P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | L | NC | P-C |
| PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH |