patternMinor
Prove that $NP^{NP\cap co-NP} = NP$
Viewed 0 times
provecapthat
Problem
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.
What should I do instead?
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.
What should I do instead?
Solution
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.
Context
StackExchange Computer Science Q#75969, answer score: 4
Revisions (0)
No revisions yet.