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

[Timothy Y. Chow]

On Mon, 18 Jan 2016, Mario Carneiro wrote:
> I don't see why it is necessary to reduce to a random bit stream here, 
> and I don't see where in Kreinovich's argument it is really necessary to 
> assume randomness. (It is true that randomness is used as part of the 
> original theoretical result, but I took this to be simply a 
> "probabilistic argument" for the existence of an oracle satisfying P^A 
> =/= NP^A.)

Perhaps Kreinovich can clarify, but if all we need is the *existence* of 
such an oracle, then this is an ancient result (Baker-Gill-Solovay).

> But we don't need to ask for all of them; the algorithm is free to look 
> at only a (necessarily polynomially large) subset of them depending on 
> the input and what it has seen before from the oracle. This too fits 
> within the "algorithm as physical experiment" model, since we can 
> perform a calculation, determine what measurement to make, and report 
> back the result of the measurement. There are exponentially many 
> measurements available for us to make, but we will not make them all, so 
> it is still feasible for a polynomial algorithm-with-measurements to act 
> like an algorithm with access to an oracle.

Well, yes, but the objection I have is, what reason do we have to think 
that such physical experiments are possible?

We can imagine building some physical machine to which you can enter the 
binary representation of a positive integer and that *deterministically* 
causes a light to go on (or not) in time polynomial in the number of bits 
that you fed in.  What is needed for the argument to go through is that we 
have the ability to build such a machine that can plausibly be thought of 
as a *random choice* from the space of *all such machines*.  I don't see 
any plausible way to do this.  The point of my previous message was to 
explain why the naive strategy of generating a fixed string of random bits 
and using it to answer queries (this was what I took Kreinovich to be 
implicitly arguing and why I thought that he needed to appeal to the 
ability to generate random bits) doesn't cut it, because it requires 
exponential work.

Tim