| > 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. |
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.