patternMinor
Prove that ${NP}^{NP}=\Sigma_2$
Viewed 0 times
sigma_2provethat
Problem
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:
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?
$\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?
Solution
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.
$$
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.
Context
StackExchange Computer Science Q#132787, answer score: 3
Revisions (0)
No revisions yet.