3 ms·

Is there any probabilistic argument around the proof? For instance, a decade before Wiles' proof of Fermat's Last Theorem, Feynman[1] showed it was extremely u

Is there any probabilistic argument around the proof? For instance, a decade before Wiles' proof of Fermat's Last Theorem, Feynman[1] showed it was extremely unlikely to be false. While you're not getting a million from Clay for that, it something non insignificant that we can use to guide our intuition. [1]http://www.lbatalha.com/blog/feynman-on-fermats-last-theorem http://www.lbatalha.com/blog/feynman-on-fermats-last-theorem

kamilner 10y ago
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