[JadeNB]

> A really cool result which seems relatively unknown is that if we augment our Turing machines with an oracle X chosen uniformly at random from all oracles then P^X =/= NP^X with probability 1.

Wait, this has to be conditional on something. If P = NP, then P^X = NP^X for any oracle X, right? (It's been a while since my theoretical CS class, so maybe it's my naïve assumption that's not true.)

[bo1024]

> If P = NP, then P^X = NP^X for any oracle X, right?

No, surprisingly, it's not true!

The problem is that a nondeterministic turing machine can ask "more" or "better" questions of an oracle than a deterministic one. Intuitively, it can ask an exponential number of questions and then accept if any of the answers turn out to be "useful".

So even if we know they solve the same problems when unaided by an oracle, this doesn't imply that an oracle amplifies their abilities in the same way.

[JadeNB]

Thanks to you and wnoise (https://news.ycombinator.com/item?id=12893051) for excellent informal explanations that nicely complement openasocket's (https://news.ycombinator.com/item?id=12893077) formal one. I love instances where intuition needs to be corrected by rigorous reasoning.

[wnoise]

It's tricky and the notation confuses things a bit.

P and NP are not the machine, but the set of problems solvable by deterministic/non-deterministic Turing machines limited to a polynomial number of steps. P^X is set of problems solvable by a deterministic Turing machine with access to oracle X, which is fairly straight forward, but need have little to with P. Similarly, NP^X is the set of problems solvable by a non-deterministic Turing machine with access to oracle X. However, this means if there's any input it could ask X to get an answer it can use to solve the problem, it can solve the problem, which may be vastly more efficient than trying to construct the right question to ask.

Essentially it boils down to: Just because two different models of computation can solve the same problems, does not mean that when augmented by the same oracle can solve the same problems (they can access the oracles in different ways).

[JadeNB]

> Essentially it boils down to: Just because two different models of computation can solve the same problems, does not mean that when augmented by the same oracle can solve the same problems (they can access the oracles in different ways).

Indeed, it was just the worry that something nasty like this could happen that made me weasel my initial definite assertion into the form of a question. Thank you for this informal explanation; it nicely complements openasocket's formal reference (https://news.ycombinator.com/item?id=12893077).

(Long-delayed post because "You are submitting too fast".)

[openasocket]

It would seem not! I found a copy of the paper: http://www.cs.cornell.edu/courses/cs682/2006sp/handouts/benn... and it doesn't seem to specify any conditions. Apparently prior work has constructed specific oracles X such that P^X != NP^X. I think the paper is "Relativization of the P =?NP question" but I couldn't find a copy. Though I did find this http://www.cs.umd.edu/~jkatz/complexity/f05/relativization.p... which might help.

[JadeNB]

Thanks for that reference! I am glad that, even if my intuition led me astray, at least I had the foresight to append the weasel "… right?" to the end of my false claim. :-)

[adilparvez]

> If P = NP, then P^X = NP^X for any oracle X, right?

Edit: No, I think. See child comment by JadeNB.

Probably wrong { Yes, since we could just not invoke the oracle. But people do this sort of stuff to study it backwards e.g. what do P^X and NP^X (and any class^X) tell us about P and NP (and any other class). }

I hope this is clearer, let {A, B, C, ...} be the set of all oracles.

For TM + A:

P^A is the class of problems that can be done in P time on this machine.

NP^A is the class of problems that can be done in NP time on this machine.

Similarly for

TM + B

TM + C ...

This theorem says that if we choose one of these oracle machines uniformly at random then P =/= NP in _its_ model of computation a.s.

This is an entirely probabilistic statement about machines that are more "powerful" than standard TMs.

[JadeNB]

> Yes, since we could just not invoke the oracle.

I think that only shows that P^X contains P and NP^X contains NP, not that P = NP implies P^X = NP^X. Indeed, my supposition that this implication holds seems to be false; openasocket (https://news.ycombinator.com/item?id=12893077) points to a paper mentioning a specific example of an oracle B so that P^B \ne NP^B. If my naïve reasoning were correct, then we'd be able to deduce that P \ne NP; but we famously can't.

[adilparvez]

Cool, I shouldn't make assumptions, thanks for the link.