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)?
$\begingroup$
$\endgroup$
8
-
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$– Joshua GrochowMar 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$– Niel de BeaudrapMar 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$– Niel de BeaudrapMar 20, 2014 at 23:24
-
2$\begingroup$ $NP^{NP}$ contains $co-NP$, so maybe that explains why it is unlikely to equal $NP$. $\endgroup$– domotorpMar 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$– Joshua GrochowMar 24, 2014 at 16:58
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
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}$.)
answered Mar 24, 2014 at 16:54