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

[Dustin Wehr]

Thanks for the thought-provoking post. I like the idea of trying to
find practical implications of random oracle results. I don't think
you're there quite yet though.

For physics problems, once experimental data is recorded using the
available equipment, we can include it in the instance of the
optimization problem. Similarly for machine learning problems, you
need to include the training and test data sets. Then, you have (quite
large) instances of purely mathematical problems. Perhaps I've
misunderstood what you meant by: "Thus, allowing to use measurement
results in computations is equivalent to allowing standard random
sequences (random oracles)"; the interpretation I have in mind is far
from accurate.

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!). There is also the breaking of
almost all cryptography in use today.
And, perhaps most dear to this mailing list, the ability to solve
most** mathematical problems just by formalizing them precisely in a
sufficiently strong axiomatic theory.

*It's possible you'd need to use a slightly larger multiplicative
constant to remain in the realm of our current knowledge, but 2 might
actually be an overestimate.

**Those that have proofs in the supplied theory that aren't too insanely long.