As mentioned elsewhere in the thread, if provided with a random oracle A, P^A != NP^A with probability 1. It's not clear though what this actually buys you, int

As mentioned elsewhere in the thread, if provided with a random oracle A, P^A != NP^A with probability 1. It's not clear though what this actually buys you, intuition wise, since it's already sort of intuitively clear that nondeterministic oracle queries are much more powerful (then again, I guess you could say the same about nondeterministic computing...) http://epubs.siam.org/doi/abs/10.1137/0210008 http://epubs.siam.org/doi/abs/10.1137/0210008 Edit: For those who are interested, the oracle separation gives you one of the few properties we can prove about the nature of any proof of P ?= NP, that it must be 'non-relativizing'. We know a few other properties of any possible proof, described here: http://www.scottaaronson.com/papers/alg.pdf http://www.scottaaronson.com/papers/alg.pdf