Polynomial hierarchy ($\mathbf{PH}$)

The polynomial hierarchy consists of decision problems described by a constant number of alternating polynomially bounded existential and universal quantifiers with a polynomial-time predicate.

A language is in ${\Sigma }_2^{\mathbf{P}}$ when membership has the form $\exists u\forall vR(x,u,v)$ for a polynomial-time predicate $R$ and polynomially bounded strings. Reversing the quantifiers defines ${\Pi }_2^{\mathbf{P}}$.

The Karp–Lipton theorem states that $\mathbf{NP}\subseteq \mathbf{P}/\mathrm{poly}$ implies that the polynomial hierarchy collapses to its second level.