Second level of the polynomial hierarchy
= Second level of the polynomial hierarchy
{title2=$\Sigma_2^{\mathbf P}$ and $\Pi_2^{\mathbf P}$}
A language is in $\Sigma_2^{\mathbf 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 $\Pi_2^{\mathbf P}$.