10 February 2010

Is P=NP a reasonable hypothesis?

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

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.

(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.)


1 Comment »

  1. […] 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 | Reply

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Blog at

%d bloggers like this: