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

[Josef Urban]

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"?
Josef
On Jan 19, 2016 12:56 AM, "Timothy Y. Chow" <tchow at alum.mit.edu> wrote:

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
_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160119/e9158dbe/attachment-0001.html>