patternMinor
Why can't we simulate an NP oracle with an NP machine?
Viewed 0 times
whycanwithmachineoraclesimulate
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#73980, answer score: 3
Revisions (0)
No revisions yet.