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

[Timothy Y. Chow]

It seems to me that most respondents have failed to understand the thrust 
of Vladik Kreinovich's argument.

For the purposes of this discussion, let's accept the usual assumption 
that if something is solvable in polynomial time by a deterministic Turing 
machine (DTM) then it is solvable in practice.  Of course this is only an 
approximation, but getting hung up on that fact will sidetrack us from the 
main point.

Kreinovich's argument is that DTM's are an inadequate model of the kinds 
of computations we can do in the real world.  He wants to argue that in 
reality, we have access to truly random bit sequences.  Here again one can 
get entangled (pun intended) in philosophical debates about quantum 
mechanics, but let me again grant this for the sake of argument.

Where I believe Kreinovich's argument breaks down is in his identification 
of such random bit sequences as *random oracles*.  To use a random bit 
string as a random oracle, we have to do something like this: Identify the 
infinite string S with a language L by letting the binary representation 
of n be in L if and only if the nth bit of S is 1.  We now declare 
ourselves to have the power of solving the problem "is x in L?" in time 
polynomial in the length of x.  Then we ask what problems we can solve 
with a DTM in polynomial time.

The trouble is that Kreinovich gives us no way of determining whether the 
nth bit of S is 1 in time polynomial in the *number of bits* of n, i.e., 
in time O(log n).  The only way I see of getting to the nth bit is to 
generate n bits, which takes time *exponential* in log n.  So I see no 
reason at all to model the power of access to random bits, or even to 
quantum-mechanical superposition, as being equivalent to access to a 
random oracle.

Complexity theorists know all this.  The standard way of modeling the 
power of having access to truly random bits is to enlarge the class P to 
the (ostensibly) larger class BPP.  Whether "P = NP" then turns into the 
question of whether BPP equals the "class of problems that can be 
efficiently verified in a world with access to random bits."  One can 
argue a bit about what that class is---perhaps one of the classes AM or 
MA---but the point is that the Rossman et al. result, while an impressive 
theoretical achievement, doesn't have any implications about any such 
question.

Tim