# Constraints

## 10 February 2010

### Is P=NP a reasonable hypothesis?

Filed under: Commentary,Question — András Salamon @ 13:00
Tags:

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

In classical logic, if $\theta$ is known to be a false proposition then it is possible to derive $\theta \Rightarrow \phi$ for any proposition $\phi$. 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 $\phi$ holds”.

However, if $\theta \Rightarrow \phi$ is true, and $\phi$ can be shown to be false, then this would allow us to conclude that $\theta$ is false. Moreover, if $\phi$ is thought to be extremely unlikely, then proving $\theta \Rightarrow \phi$ would provide (weak) evidence that $\theta$ 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.