[FOM] P =? NP: A practically important breakthrough

[Timothy Y. Chow]

On Tue, 19 Jan 2016, Josef Urban wrote:
> This may be off-topic, ignorant, or subsumed by what others wrote, but I
> have always wondered why people so easily assume "randomness of the physical
> world" in their arguments. Haven't they read we are "most likely" simulated
> - www.simulation-argument.com ? Or does quantum theory really clearly
>   show randomness of the "physical world"?

It is possibly off-topic but I'll let the moderators decide that.

In terms of why people "easily assume" it, I think that one reason is that 
for many purposes, it doesn't really matter whether the physical world is 
"really random."  Modeling certain physical phenomena *as if they were 
random* is a very successful scientific technique, even in cases where we 
know that the phenomena are *not* random.  In many cases, all that matters 
is that the phenomena are *unpredictable*.

In complexity theory, many people believe that P = BPP; i.e., that true 
randomness does not help us compute anything in polynomial time that we 
can't do using a *pseudorandom* number generator.  It is probably even 
more widely believed that there are pseudorandom number generators that 
cannot be statistically distinguished from true randomness by a polynomial 
time algorithm, and therefore are unpredictable in practice.  These 
conjectures could be interpreted as saying that as far as feasible 
computation is concerned, (1) it is harmless to assume true randomness, 
and (2) strong pseudorandomness is just as unpredictable as true 
randomness.

Quantum theory, assuming it is correct, doesn't quite prove that there is 
true randomness in the world, although it comes close.  Certain naive 
deterministic views of the world are ruled out.  Bell's theorem and the 
Conway-Kochen "free will theorem" have been discussed on FOM before.  It 
is still possible to interpret quantum mechanics deterministically, but 
one needs to appeal to fairly exotic concepts such as de Broglie-Bohm 
pilot waves.

By the way, in my opinion the best popular description of the essential 
"puzzle" underlying quantum mechanics is the opening chapter of the book 
"Schroedinger's Rabbits" by Colin Bruce.  If you want to understand why it 
is so difficult to explain quantum phenomena without appealing to 
randomness then I highly recommend reading this chapter.

Tim