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

[David Diamondstone]

On Wed, Jan 13, 2016 at 10:19 AM Kreinovich, Vladik <vladik at utep.edu> wrote:

>  The above 2015 result states, in particular, that for a random
>
> oracle A, NP^A is different from P^A. Thus, what
>
> Rossman-Servedio-Tan theorem says is that if we consider
>
> _practical_ problems, then there exist practical problems for
>
> which no feasible algorithm is possible. In other words, THIS
>
> THEOREM PROVIDES THE ANSWER TO EXACTLY THE QUESTION THAT IS BEHIND
>
> THE MATHEMATICAL FORMULATION OF THE P =? NP PROBLEM.
>
If this interpretation is correct, then you should, at least in principle,
be able to give me an example of such a problem. But what is the example?

I don't think think this is a valid interpretation, for the following
reason: if you know that $NP^A \neq P^A$ for almost every A, then for
almost every A there is some decision problem $f \in NP^A \setminus P^A$.
But would you claim that this problem f is "practically verifiable but not
practically solvable"? I don't think so. The fact that $f \in NP^A$ for
some particular random oracle $A$ does not allow me to verify it, because
in practice if I can generate random bits, I can pretend I have some random
oracle B (the result of my bit generation procedure). But I don't have
access to A, and there's no reason to believe that f will be in NP^B.

What is missing from the statement that $NP^A \neq P^A$ for almost every A
to a "practical" separation between the solvable and the verifiable is some
sort of uniformity.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160120/a0c1b299/attachment-0001.html>