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?

  • 1
    $\begingroup$ We don't know whether $\textbf{NP}^\textbf{NP} \neq \textbf{NP}$, so it will be hard coming up with such an example. Note that $\textbf{NP}^\textbf{NP} = \Sigma^P_2$ (the second level of the polynomial hierarchy, $\textbf{PH}$). $\endgroup$ – Pål GD Jun 6 '18 at 20:34
  • $\begingroup$ @PålGD Yeah, that's why I said "under reasonable assumptions". Certainly no example can be shown to work unconditionally. Maybe it's still a hard question though. $\endgroup$ – tparker Jun 6 '18 at 20:40
  • $\begingroup$ But there are many problems (e.g. maxmin problems) that are complete for $\Sigma^P_2$. $\endgroup$ – Pål GD Jun 6 '18 at 20:53
  • $\begingroup$ Take a look at the first reference in a previous answer. $\endgroup$ – Pål GD Jun 6 '18 at 20:54
  • $\begingroup$ @PålGD Thanks, but understanding those examples requires going through reductions complicated enough that I lose all the intuition. By a "simple" example I mean one which I can understand by directly thinking about the behavior of a NTM, without needing to go through a lot of nonobvious other results. $\endgroup$ – tparker Jun 6 '18 at 21:02

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.


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.