Prove that ${NP}^{NP}=\Sigma_2$

Question

I've head the lecture today and we saw this theorem:

$\mathsf{NP}^{\mathsf{NP}}=\Sigma_2$

But without a proof.

Here are the definitions I use:

A language $L$ belongs to $\Sigma_k$ if there is a deterministic Turing machine $M(x,y_1,y_2,\dots,y_k)$ such that:

• There exists a constant $c$ such that $|y_i|=|x|^c$ and $M(x,y_1,y_2,\dots,y_k)$ runs in time $\mathit{poly}(|x|)$.
• $x\in L$ iff $\exists_{y_1}\forall_{y_2}\exists_{y_3} \dots M(x,y_1,y_2,\dots,y_k)=T$,
  where the quantifiers are alternating between existential and universal, and start with existential.

$\mathsf{NP}^{\mathsf{NP}}$ is the class of all languages of languages in $\mathsf{NP}$ with oracle calls to a language in $\mathsf{NP}$.

I thought maybe to use $\mathsf{SAT}$ as it is an $\mathsf{NP}$-complete language.

Can someone please help me understand why this is true?

Answer 1

Suppose first that $L \in \Sigma_2^P$. Then there exists a machine $T(x,y,z)$, running in time $\mathit{poly}(|x|)$, such that $$ x \in L \Leftrightarrow \exists y \forall z \, M(x,y,z) = T $$ Using the reduction in Cook's theorem, given $x,y$, we can express $\exists z \, M(x,y,z) = T$ as a SAT instance. Therefore given a SAT oracle, we can verify that $y$ satisfies $\forall z \, M(x,y,z)$. This shows that $L \in \mathsf{NP}^{\mathsf{NP}}$.

In the other direction, suppose that $L \in \mathsf{NP}^{\mathsf{NP}} = \mathsf{NP}^{\mathsf{SAT}}$. There is thus an oracle Turing machine $M(x,y)$, running in time $\mathit{poly}(|x|)$, such that $$ x \in L \Leftrightarrow \exists y \, M^{\mathsf{SAT}}(x,y) = T. $$ (The notation $M^{\mathsf{SAT}}$ means running $M$ with a SAT oracle.)

How can we tell that $M^{\mathsf{SAT}}(x,y) = T$ without access to a SAT oracle? The idea is to "guess" the answer of every SAT query, and prove the necessary information to verify this answer. Suppose that $M$ queries $q \stackrel?\in \mathsf{SAT}$. If $q \in \mathsf{SAT}$ then we can provide a witness for it, namely a satisfying assignment. If $q \notin \mathsf{SAT}$ then we know that every assignment does not satisfy $q$.

Accordingly, we construct a machine $M'(x,y',z')$ in the following way. The witness $y'$ consists of the original witness $y$, together with the following information: the number of SAT queries performed by $M$; for each SAT query $q_i$, the answer $b_i$; for each positive answer, the corresponding satisfying assignment $a_i$. The "cowitness" $z'$ consists of an assignment $a_i$ for each negative answer to a SAT query.

The machine $M'$ acts simulates $M$. Whenever $M$ makes a SAT query $q_i$, it determines the answer from $y'$. If $b_i = T$, it verifies that $a_i$ is a satisfying assignment for $q_i$. If $b_i = F$, it verifies that $a_i$ is not a satisfying assignment for $q_i$. The new machine $M'$ accepts if all verifications succeed, and additionally $M$ accepts.

This shows that $L \in \Sigma_2$, completing the proof of your statement.