 Second level of the polynomial hierarchy

ID: second-level-of-the-polynomial-hierarchy

A language is in

Σ_{2}^{P}

when membership has the form

\exists u \forall v R (x, u, v)

for a polynomial-time predicate

R

and polynomially bounded strings. Reversing the quantifiers defines

Π_{2}^{P}

 New to topics? Read the docs here!