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

[Mario Carneiro]

On Mon, Jan 18, 2016 at 12:32 PM, Timothy Y. Chow <tchow at alum.mit.edu>
wrote:

> 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.
>

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.) My knowledge is
admittedly weak in this area, but from your definition it seems that an
oracle should be able to answer questions of the form "x in L" for some
language L (a subset of {0,1}*). Furthermore, the strings in question will
have length polynomial in the input n, so that in theory we have access to
exponentially many "random bits" from our oracle.

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.

Another point of contention might be the approximation that there is enough
information in reality that physical measurements can actually act like a
(random) oracle. For example one might measure the thickness of a rod
somewhere along its length, with the location being delivered by a bit
string of length logarithmic in the length of the rod, but the rod can only
be subdivided so many times before atomic effects make it impossible to
continue. Measuring quantum bits might be a way to produce randomness, but
if the bits are all random then measuring one bit is as good as any other
and it devolves into a random bit string, which does not have enough data
in it by Tim Chow's argument.

Mario Carneiro
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160118/2fd144a7/attachment.html>