3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Use the other part of your assumption on $A$ too. ​ ​ $\endgroup$ – user12859 May 28 '17 at 11:29
  • $\begingroup$ @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. $\endgroup$ – Covvar May 28 '17 at 11:36
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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