Does it even make sense to ask “what if P = NP?”, or is this nonsense?

In classical logic, if is known to be a false proposition then it is possible to derive for any proposition . So arguing from falsehood has a bad reputation.

The consensus is that P is strictly contained in NP. If this is the case, then P = NP is a false proposition, so the common wisdom is that we should not be interested in statements of the form “if P = NP, then holds”.

However, if is true, and can be shown to be false, then this would allow us to conclude that is false. Moreover, if is thought to be extremely unlikely, then proving would provide (weak) evidence that was also likely to be false.

Following on from the previous post, the question is then: *are there some extremely unlikely consequences of P = NP*?

Richard Lipton has argued that P = NP may lead to less surprising things than if P were not equal to NP. Epistemologically speaking, we should then perhaps give greater credence to the claim that P may equal NP, if only as a basis for deriving some interesting consequences. We could then decide which is more likely: stuff that P = NP predicts, or results that follow if P is strictly contained in NP.

*(Edit 20100224: added link to xkcd strip.)*

*(Edit 20100815: note Timothy Gowers discusses P = NP as a hypothesis in the context of the Deolalikar manuscript, which uses this strategy.)*

### Like this:

Like Loading...

*Related*

[…] in the unlikeliness of FPT = W[1]. (I discussed this kind of conditional result in a previous post, Is P=NP a reasonable hypothesis?) Note that the abstract in the original version has a typo, the should be an equality. […]

Pingback by CCC 2010 « Constraints — 14 June 2010 @ 20:56 |