[proofplan]
The first equality is a direct comparison of definitions: the existentially quantified polynomial-time predicate defining $\Sigma_1^P$ is exactly an NP verifier with a polynomially bounded certificate. For the universal level, we take complements: a universal condition fails exactly when there exists a polynomially bounded witness to its failure. This converts $\Pi_1^P$ into complements of NP languages, and conversely converts complements of NP languages into universal first-level predicates.
[/proofplan]
[step:Identify existential first-level predicates with NP verifiers]
Let $L \subseteq \{0,1\}^*$ be a language.
First suppose $L \in \Sigma_1^P$. By definition of $\Sigma_1^P$, there exist a polynomial $p: \mathbb{N} \to \mathbb{N}$ and a polynomial-time decidable predicate
$R: \{0,1\}^* \times \{0,1\}^* \to \{0,1\}$
such that, for every $x \in \{0,1\}^*$,
\begin{align*}
x \in L \iff \exists y \in \{0,1\}^* \text{ with } |y| \le p(|x|) \text{ and } R(x,y)=1.
\end{align*}
Define a verifier
$V: \{0,1\}^* \times \{0,1\}^* \to \{0,1\}$
by $V(x,y)=R(x,y)$. Since $R$ is decidable in polynomial time, $V$ runs in polynomial time. The same polynomial $p$ bounds certificate length. Hence $L \in NP$.
Conversely, suppose $L \in NP$. By the verifier definition of $NP$, there exist a polynomial $p: \mathbb{N} \to \mathbb{N}$ and a polynomial-time verifier
$V: \{0,1\}^* \times \{0,1\}^* \to \{0,1\}$
such that, for every $x \in \{0,1\}^*$,
\begin{align*}
x \in L \iff \exists y \in \{0,1\}^* \text{ with } |y| \le p(|x|) \text{ and } V(x,y)=1.
\end{align*}
Define
$R: \{0,1\}^* \times \{0,1\}^* \to \{0,1\}$
by $R(x,y)=V(x,y)$. Then $R$ is polynomial-time decidable, and the displayed equivalence is exactly the defining condition for $L \in \Sigma_1^P$. Therefore $NP \subseteq \Sigma_1^P$.
Combining both inclusions gives
\begin{align*}
\Sigma_1^P = NP.
\end{align*}
[guided]
We compare the two definitions without changing any computational content. A language $L \subseteq \{0,1\}^*$ lies in $\Sigma_1^P$ precisely when membership in $L$ can be expressed by a polynomially bounded existential certificate checked by a polynomial-time predicate. That is, there are a polynomial $p: \mathbb{N} \to \mathbb{N}$ and a polynomial-time decidable predicate
$R: \{0,1\}^* \times \{0,1\}^* \to \{0,1\}$
such that, for every input string $x \in \{0,1\}^*$,
\begin{align*}
x \in L \iff \exists y \in \{0,1\}^* \text{ with } |y| \le p(|x|) \text{ and } R(x,y)=1.
\end{align*}
This is exactly the verifier definition of $NP$: the string $y$ is the certificate, the polynomial $p$ bounds its length, and the predicate $R$ is the verifier computation.
Formally, if $L \in \Sigma_1^P$, define
$V: \{0,1\}^* \times \{0,1\}^* \to \{0,1\}$
by $V(x,y)=R(x,y)$. Since $R$ is decidable in polynomial time, $V$ is a polynomial-time verifier. The same polynomial $p$ gives the certificate bound, so the displayed equivalence proves $L \in NP$.
For the reverse inclusion, suppose $L \in NP$. Then there are a polynomial $p: \mathbb{N} \to \mathbb{N}$ and a polynomial-time verifier
$V: \{0,1\}^* \times \{0,1\}^* \to \{0,1\}$
such that, for every $x \in \{0,1\}^*$,
\begin{align*}
x \in L \iff \exists y \in \{0,1\}^* \text{ with } |y| \le p(|x|) \text{ and } V(x,y)=1.
\end{align*}
Now define
$R: \{0,1\}^* \times \{0,1\}^* \to \{0,1\}$
by $R(x,y)=V(x,y)$. The predicate $R$ is polynomial-time decidable because $V$ is polynomial-time, and the same existential characterization proves $L \in \Sigma_1^P$. Thus both inclusions hold, and therefore $\Sigma_1^P = NP$.
[/guided]
[/step]
[step:Turn universal first-level predicates into complements of NP languages]
Let $L \subseteq \{0,1\}^*$.
Suppose $L \in \Pi_1^P$. By definition, there exist a polynomial $p: \mathbb{N} \to \mathbb{N}$ and a polynomial-time decidable predicate
$R: \{0,1\}^* \times \{0,1\}^* \to \{0,1\}$
such that, for every $x \in \{0,1\}^*$,
\begin{align*}
x \in L \iff \forall y \in \{0,1\}^* \text{ with } |y| \le p(|x|), R(x,y)=1.
\end{align*}
Let $\overline{L} := \{x \in \{0,1\}^* : x \notin L\}$ denote the complement of $L$. Negating the displayed equivalence gives, for every $x \in \{0,1\}^*$,
\begin{align*}
x \in \overline{L} \iff \exists y \in \{0,1\}^* \text{ with } |y| \le p(|x|) \text{ and } R(x,y)=0.
\end{align*}
Define
$S: \{0,1\}^* \times \{0,1\}^* \to \{0,1\}$
by $S(x,y)=1-R(x,y)$. Since $R$ is polynomial-time decidable, $S$ is polynomial-time decidable. Hence $\overline{L} \in NP$, so $L \in coNP$. Therefore $\Pi_1^P \subseteq coNP$.
[/step]
[step:Turn complements of NP languages into universal first-level predicates]
Suppose $L \in coNP$. By definition of $coNP$, its complement
$\overline{L} := \{x \in \{0,1\}^* : x \notin L\}$
belongs to $NP$. Hence there exist a polynomial $p: \mathbb{N} \to \mathbb{N}$ and a polynomial-time verifier
$V: \{0,1\}^* \times \{0,1\}^* \to \{0,1\}$
such that, for every $x \in \{0,1\}^*$,
\begin{align*}
x \in \overline{L} \iff \exists y \in \{0,1\}^* \text{ with } |y| \le p(|x|) \text{ and } V(x,y)=1.
\end{align*}
Negating this equivalence gives
\begin{align*}
x \in L \iff \forall y \in \{0,1\}^* \text{ with } |y| \le p(|x|), V(x,y)=0.
\end{align*}
Define
$R: \{0,1\}^* \times \{0,1\}^* \to \{0,1\}$
by $R(x,y)=1-V(x,y)$. Since $V$ is polynomial-time decidable, $R$ is polynomial-time decidable. The preceding equivalence becomes
\begin{align*}
x \in L \iff \forall y \in \{0,1\}^* \text{ with } |y| \le p(|x|), R(x,y)=1.
\end{align*}
This is the defining condition for $L \in \Pi_1^P$. Therefore $coNP \subseteq \Pi_1^P$.
Combining this inclusion with $\Pi_1^P \subseteq coNP$ gives
\begin{align*}
\Pi_1^P = coNP.
\end{align*}
[/step]
