Does $\mathsf{NP^{NP \,\cap\, coNP}=NP}$ hold?

Clearly $\mathsf{NP^{NP}\neq NP}$, but it seems to me that $\mathsf{NP\cap coNP}$ is "deterministic" which makes me believe this is true.

Is there a simple proof (or maybe just by definition)?

  • 6
    $\begingroup$ First, yes. Indeed, an oracle $A$ satisfies $\mathsf{NP}^{A} = \mathsf{NP}$ if and only if $A \in \mathsf{NP} \cap \mathsf{coNP}$. This class is called $\mathsf{Low(NP)}$ or sometimes $\mathsf{L_1 P}$: complexityzoo.uwaterloo.ca/Complexity_Zoo:L#lkp. Second, I don't think it's at all clear that $\mathsf{NP}^{\mathsf{NP}} \neq \mathsf{NP}$, although this is a widely-held belief. In particular, it implies $\mathsf{P} \neq \mathsf{NP}$ and appears to be strictly stronger, as there is no relativizable implication the other way. $\endgroup$ Mar 20, 2014 at 23:18
  • 2
    $\begingroup$ Also, people who believe that FACTORING is difficult may take issue with your intuition that $\mathsf{NP \cap coNP}$ is "deterministic". $\endgroup$ Mar 20, 2014 at 23:21
  • 9
    $\begingroup$ @JoshuaGrochow: I think you should add that as an answer, with some exposition as to what the classes in the low hierarchy are; it's about as good an answer as the OP is likely to get. $\endgroup$ Mar 20, 2014 at 23:24
  • 2
    $\begingroup$ $NP^{NP}$ contains $co-NP$, so maybe that explains why it is unlikely to equal $NP$. $\endgroup$
    – domotorp
    Mar 21, 2014 at 13:11
  • 4
    $\begingroup$ @NieldeBeaudrap: My hesitancy at posting it as an answer rather than comment was that, although I believe maomao genuinely asked this question in earnest, it can be, and has been in the past, given as a homework exercise. $\endgroup$ Mar 24, 2014 at 16:58

1 Answer 1


Yes. Indeed, an oracle $A$ satisfies $\mathsf{NP}^A=\mathsf{NP}$ if and only if $A \in \mathsf{NP} \cap \mathsf{coNP}$. This class is called $\mathsf{Low(NP)}$ or sometimes $\mathsf{L_1 P}$ (see the link and the paper cited there for more of an explanation of the low hierarchy in general).

Your intuition about "determinism" is actually somewhat correct (although it's not deterministic enough for us to conclude $\mathsf{P} = \mathsf{NP} \cap \mathsf{coNP}$). Try this as an exercise and you'll see this intuition vindicated: first show - carefully, spelling out the details - that if $A \in \mathsf{P}$, then $\mathsf{NP}^{A} = \mathsf{NP}$. Figure out exactly the part of your proof that doesn't work if you only assume $A \in \mathsf{NP}$, and then realize why that part does work when $A \in \mathsf{NP} \cap \mathsf{coNP}$.

(Showing the converse is not too difficult either: $\mathsf{NP}^A = \mathsf{NP}$ implies $A \in \mathsf{NP} \cap \mathsf{coNP}$.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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