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

[Arnold Neumaier]

On Wed, January 13, 2016 22:54, Joe Shipman wrote:
> This doesn't seem to make it more plausible that the specific well-defined
> statement P=NP is false. I disagree that the random oracle results are the
> ones that are "practically important", because if there is a fast
> classical algorithm for SAT it would have colossal practical consequences.

A proof of P=NP would probably have immense practical consequences, since
it would produce polynomial algorithms for all NP-complete problems,
including SAT and integer programming.

However, a poof of the opposite would just validate that the observed
state of the art is a realistic expression of what one can expect, hence
would have no practical consequences at all. (It would have strong
consequences for proving lower bounds in complexity theory, though.)

Arnold Neumaier