[FOM] P =? NP: A practically important breakthrough (Kreinovich, Vladik)

[Arnold Neumaier]

On Fri, January 15, 2016 15:47, Dustin Wehr wrote:

> There's a fun game we can play that demonstrates how profoundly far
> from resolving "THE QUESTION THAT IS BEHIND THE MATHEMATICAL
> FORMULATION OF THE P =? NP PROBLEM" we are: supposing we had, say, a 1
> MB C program that solves size n instances of SAT in, say, 2n + (1
> million) operations*, what are some of the most extraordinary things we
> could accomplish? I haven't played it all the way, but I bet one can
> show that we could achieve sci-fi level AI in not too long on our
> personal computers (or smart phones!).

But P=NP might imply only that you can solve size n instances of SAT in,
say, n^(1 million) operations. This is polynomial but has no use at all.
Thus even when P=NP would have been proved, it might be a lot of work to
find out which problems become tractable in a real life sense...

Arnold Neumaier