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}}$.

A propositional formula with two blocks of quantified Boolean variables. Determining the truth of an existential-then-universal instance is a canonical complete problem for the existential second level of the polynomial hierarchy, ${\Sigma }_2^{\mathrm{P}}$. For completeness one may restrict the matrix $\psi$ to a disjunction of terms with at most three literals. The order of the quantifiers matters: the assignment to $X$ must work for every assignment to $Y$.

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