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 P^PP (the class of problems that are decidable by a polynomial time Turing machine with an access to PP oracle) and PSPACE.

Important complexity classes

P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | NC | P-C

PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH