= Solution
This is the <Karp–Lipton theorem>. It is enough to place $\Pi_2^{\mathbf P}$ inside $\Sigma_2^{\mathbf P}$. Let $L\in\Pi_2^{\mathbf P}$, so for a polynomial-time predicate $R$ and polynomially bounded strings,
$$
x\in L
\quad\Longleftrightarrow\quad
\forall y\ \exists z\ R(x,y,z).
$$
The NP search problem that receives $(x,y)$ and seeks such a $z$ has, by part (i), a <polynomial-size circuit family> producing a valid witness whenever one exists. For each input length there is therefore a polynomial-size circuit $C$ such that, for every relevant $x,y$, existence of a witness implies $R(x,y,C(x,y))$.
Consequently
$$
x\in L
\quad\Longleftrightarrow\quad
\exists C\ \forall y\ R(x,y,C(x,y)),
$$
where the existentially guessed circuit description has polynomial length and evaluation of $C$ is polynomial time. This is a $\Sigma_2^{\mathbf P}$ description. Hence $\Pi_2^{\mathbf P}\subseteq\Sigma_2^{\mathbf P}$; complementation gives the reverse inclusion, and merging adjacent equal quantifier blocks collapses every higher level. Thus the <polynomial hierarchy> satisfies
$$
\boxed{\mathbf{PH}=\Sigma_2^{\mathbf P}.}
$$
Back to article page
