snippetMinor
Specific example of a problem that shows why **NP** isn't low for itself
Viewed 0 times
itselfproblemwhylowexampleshowsthatforspecificisn
Problem
Wikipedia says
Every class which is low for itself is closed under complement, provided that it is powerful enough to negate the boolean result. This implies that NP isn't low for itself unless NP = co-NP, which is considered unlikely... .
This line of reasoning is a bit abstract for me. Is there a concrete example of a simple problem that can be shown to be in $\textbf{NP}^\textbf{NP} \setminus \textbf{NP}$ under reasonable assumptions? That is, a problem that can't be solved efficiently by a nondeterministic Turing machine, but can be solved efficiently by a NTM with oracle access to another NTM?
Every class which is low for itself is closed under complement, provided that it is powerful enough to negate the boolean result. This implies that NP isn't low for itself unless NP = co-NP, which is considered unlikely... .
This line of reasoning is a bit abstract for me. Is there a concrete example of a simple problem that can be shown to be in $\textbf{NP}^\textbf{NP} \setminus \textbf{NP}$ under reasonable assumptions? That is, a problem that can't be solved efficiently by a nondeterministic Turing machine, but can be solved efficiently by a NTM with oracle access to another NTM?
Solution
As Pål GD mentions in the comments, $\mathsf{NP}^\mathsf{NP}$ is usually knows as $\mathsf{\Sigma}_2^P$, the second level of the polynomial hierarchy. If $L$ is any $\mathsf{\Sigma}_2^P$ complete problem, then $\mathsf{NP} \neq \mathsf{\Sigma}_2^P$ is equivalent to $L \in \mathsf{\Sigma}_2^P \setminus \mathsf{NP}$. So any $\mathsf{\Sigma}_2^P$-complete problem is a concrete example for a problem in $\mathsf{\Sigma}_2^P \setminus \mathsf{NP}$ under the reasonable assumption that $\mathsf{\Sigma}_2^P \setminus \mathsf{NP} \neq \emptyset$. In other words, these are the problems "most likely" to be the concrete examples you seek.
One canonical complete problem for $\mathsf{\Sigma}_2^P$ is $\exists \forall\mathsf{SAT}$: given a formula $\varphi$ on variables $\vec{x},\vec{y}$, is is true that there exists an assignment $\alpha$ to $\vec{x}$ such that $\varphi|_{\vec{x} = \alpha}$ becomes a tautology? It is easy to see that this can be solved by an $\mathsf{NP}^\mathsf{NP}$ machine: the machine guesses $\alpha$, and uses the oracle to verify that $(\lnot \varphi)|_{\vec{x} = \alpha}$ is unsatisfiable.
Generally speaking, the assumption $\mathsf{NP} \neq \mathsf{\Sigma}_2^P$ seems stronger than $\mathsf{P} \neq \mathsf{NP}$, and when proving conditional results, we prefer assuming the latter rather than the former. But it is generally conjectured that the entire polynomial hierarchy is strict, a much stronger assumption.
One canonical complete problem for $\mathsf{\Sigma}_2^P$ is $\exists \forall\mathsf{SAT}$: given a formula $\varphi$ on variables $\vec{x},\vec{y}$, is is true that there exists an assignment $\alpha$ to $\vec{x}$ such that $\varphi|_{\vec{x} = \alpha}$ becomes a tautology? It is easy to see that this can be solved by an $\mathsf{NP}^\mathsf{NP}$ machine: the machine guesses $\alpha$, and uses the oracle to verify that $(\lnot \varphi)|_{\vec{x} = \alpha}$ is unsatisfiable.
Generally speaking, the assumption $\mathsf{NP} \neq \mathsf{\Sigma}_2^P$ seems stronger than $\mathsf{P} \neq \mathsf{NP}$, and when proving conditional results, we prefer assuming the latter rather than the former. But it is generally conjectured that the entire polynomial hierarchy is strict, a much stronger assumption.
Context
StackExchange Computer Science Q#92812, answer score: 3
Revisions (0)
No revisions yet.