4
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Yuval Filmus
    Nov 29 '20 at 14:34
  • $\begingroup$ I've edited the question $\endgroup$
    – convxy
    Nov 29 '20 at 14:47
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – convxy
    Nov 29 '20 at 17:30
  • $\begingroup$ Take it as an exercise. $\endgroup$
    – Yuval Filmus
    Nov 29 '20 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.