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

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.

• The first step is writing the definitions of $\mathsf{NP}^{\mathsf{NP}}$ and $\Sigma_2^P$. Since these are not completely standard (in the sense that there are several common equivalent definitions), perhaps you'd like to add the definitions you've seen in class? – Yuval Filmus Nov 29 '20 at 14:34
• I've edited the question – convxy Nov 29 '20 at 14:47

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.

• about the first part- I'm not sure I understood how to use the oracle to $\mathsf{SAT}$ to verify for all assignments $z$ that $M(x,y,z)=T$? it doesn't it take exponential time? – convxy Nov 29 '20 at 17:30
• Take it as an exercise. – Yuval Filmus Nov 29 '20 at 17:32