[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*}[/step]

[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: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]