# Prove that $NP^{NP\cap co-NP} = NP$

Let $A\in NP\cap co-NP$. Then, $NP^A = NP$.

At first, I thought: Easy, let $L\in NP^A$ s.t. $A\in NP\cap co-NP$. Let $M_L$, an $NDTM$ to decide $L$ and $M_A$, an $NDTM$ to decide $A$. Then, we could create a new $NDTM$, $M$ which acts the same as $M_L$, but instead of calling the oracle, it simulates $M_A$ on the oracle's input.

That is wrong as far as I understand; We can't simulate an $NDTM$ that way since $M_A$ may have some computation paths which rejects and some which accepts and we wouldn't know how to act.

• Use the other part of your assumption on $A$ too. ​ ​ – user12859 May 28 '17 at 11:29
• @RickyDemer, I guess you're referring to the fact that $A$ is also in $co-NP$. In other words, $A^c\in NP$ and so, it has it's own $TM$. I tried to think of some ways using both $M_A$ and $M_{A^c}$ (i.e. simulating them together) but couldn't figure it out. – Covvar May 28 '17 at 11:36
Since $A \in \mathsf{NP} \cap \mathsf{coNP}$, there is a witness both for $x \in A$ and for $x \notin A$. An NP machine which wishes to (non-deterministically) find out whether $x \in A$ or not can guess the answer ($x \in A$ or $x \notin A$) and then verify it using a witness.