3
$\begingroup$

In this question : Does $NP^{NP}=NP$? ,
it says that one of the reason is that we don't know how to detect 'no' answers from the oracle.
Why is that true though? There is an NTM for any language L in NP, that runs in polynomial time. IIRC we can simulate the NTM with a deterministic TM M that runs in exponential time, that tries every non-deterministic option, and decides L... So why can't we simulate the oracle using that M in another NP machine?

Thanks.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ That answer says we don't know how the NP machine could detect 'no' answers from the oracle, not that we don't know how to detect them at all. ​ ​ $\endgroup$ – user12859 Apr 15 '17 at 14:08
  • $\begingroup$ So the problem is that even if we get a 'no' from the simulation, there could still be an accepting branch? $\endgroup$ – Bar Apr 15 '17 at 15:23
  • $\begingroup$ Yes. ​ ​ ​ ​ ​ ​ ​ Contrast that with how ​ ​ ​ $(\text{NP} \cap \text{coNP})^{\text{NP} \cap \text{coNP}}$ ​ = ​ $\text{NP} \cap \text{coNP}$ ​ ​ ​ and ​ ​ ​ $\text{NP}^{\text{NP} \cap \text{coNP}}$ ​ = ​ NP $\hspace{.14 in}$ are both known to hold, since for those oracles, there's a witness regardless of what the answer is. $\hspace{.24 in}$ $\endgroup$ – user12859 Apr 15 '17 at 16:56
3
$\begingroup$

You don't have exponential time, what you have is a nondeterministic polynomial time machine.

What you can try to do, in order to simulate the oracle call to $\mathcal{O}\in NP$ on a string $s$, is to run the nondeterminstic polynomial machine $M_\mathcal{O}$ on input $s$. If $M_\mathcal{O}$ returned "yes" then you know $s\in\mathcal{O}$, but if it returned "no", then you cant be sure, and you don't have enough resources to try out all possible branches in an NP machine.

| cite | improve this answer | |
$\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.