Problem Detail: I know its silly, but i managed to confuse myself and i need help settling this Suppose $P=NP$, then clearly for every oracle $A$ we have $P^A=NP^A$ which contradicts the fact that there exists some oracle $A$ for which $P^Aneq NP^A$, hence $Pneq NP$ Whats wrong? Thanks!
Asked By : Ariel
Answered By : usul
Sure, you just have to be careful thinking about what it means to have an oracle. The problem comes from an annoying abuse of notation we use in CS: In the statement $P=NP$, $P$ refers to a set of languages. But in the statement $P^A = NP^A$, $P$ refers to a class of Turing Machines (determinstic polytime TMs). You should think of these two $P$s as of completely different types. So even if the two sets of languages $P$ and $NP$ are the same, deterministic polytime TMs still do not work in the same way as nondeterministic ones. In particular, given an oracle, a nondeterministic TM can “ask many questions at once”, which is something the regular TM cannot do. So even if they decide the same set of languages when neither type of machine is given additional help, the oracle might help one type of machine more than another.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/37626 Ask a Question Download Related Notes/Documents
