<p>Yes. Indeed, an oracle $A$ satisfies $\mathsf{NP}^A=\mathsf{NP}$ if and only if $A \in \mathsf{NP} \cap \mathsf{coNP}$. This <a href="http://complexityzoo.uwaterloo.ca/Complexity_Zoo:L#lkp">class is called $\mathsf{Low(NP)}$ or sometimes $\mathsf{L_1 P}$</a> (see the link and the paper cited there for more of an explanation of the low hierarchy in general).</p>

<p>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}$.</p>

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

CC BY-SA 3.0
2014-03-24T16:54:49.467Z
2014-03-24T16:54:49.467Z
Joshua Grochow
<p>Does $\mathsf{NP^{NP \,\cap\, coNP}=NP}$ hold?</p>

<p>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. </p>

<p>Is there a simple proof (or maybe just by definition)? </p>

CC BY-SA 3.0
2014-03-20T23:18:23.140Z
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}$: https://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.
Joshua Grochow
CC BY-SA 3.0
2014-03-20T23:21:33.367Z
Also, people who believe that FACTORING is difficult may take issue with your intuition that $\mathsf{NP \cap coNP}$ is "deterministic".
Niel de Beaudrap
CC BY-SA 3.0
2014-03-20T23:24:27.537Z
@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.
Niel de Beaudrap
CC BY-SA 3.0
2014-03-21T13:11:17.193Z
$NP^{NP}$ contains $co-NP$, so maybe that explains why it is unlikely to equal $NP$.
domotorp
CC BY-SA 3.0
2014-03-24T16:58:10.540Z
@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.
Joshua Grochow
CC BY-SA 3.0
2014-03-24T18:13:05.657Z
@domotorp: I understand why it is *unlikely* that $NP^{NP} \neq NP$, but the question says it is "clearly" the case. "Clearly" (in technical usage) usually denotes "It is so easy to prove that it's not even worth writing out the proof"...
Joshua Grochow
CC BY-SA 3.0
2014-03-24T19:19:20.430Z
@JoshuaGrochow: fair enough, though this would be an argument against writing your comment as well, which if not a complete answer provides a very short reduction to the location of a complete answer.
Niel de Beaudrap
CC BY-SA 3.0
2014-03-24T19:44:52.587Z
@NieldeBeaudrap: Well, I did post the answer eventually :).
Joshua Grochow
<cc.complexity-theory><complexity-classes><oracles>
$\mathsf{NP} \cap \mathsf{coNP}$ as oracle
maomao
# $\mathsf{NP} \cap \mathsf{coNP}$ as oracle

(Asked by: username_0 on 2014-03-20)

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)?

**Tags:** cc.complexity-theory, complexity-classes, oracles
> **Comments:**
> **username_1**: 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}$: https://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.  
> **username_2**: Also, people who believe that FACTORING is difficult may take issue with your intuition that $\mathsf{NP \cap coNP}$ is "deterministic".  
> **username_2**: @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.  
> **username_3**: $NP^{NP}$ contains $co-NP$, so maybe that explains why it is unlikely to equal $NP$.  
> **username_1**: @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.  
> **username_1**: @domotorp: I understand why it is *unlikely* that $NP^{NP} \neq NP$, but the question says it is "clearly" the case. "Clearly" (in technical usage) usually denotes "It is so easy to prove that it's not even worth writing out the proof"...  
> **username_2**: @JoshuaGrochow: fair enough, though this would be an argument against writing your comment as well, which if not a complete answer provides a very short reduction to the location of a complete answer.  
> **username_1**: @NieldeBeaudrap: Well, I did post the answer eventually :).  

---

## 1 answers

### Answer by username_1 on 2014-03-24. Score: 15

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}$](http://complexityzoo.uwaterloo.ca/Complexity_Zoo:L#lkp) (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}$.)


---

