During the discussion about Vinay Deolalikar’s manuscript, many people commented about the consequences that would follow if we knew that P ≠ NP. I’d like to discuss these consequences in a little more detail.

This is the counterpart to the question of what would happen if we knew that P = NP. Neither question has anything to do with whether a particular attempt at a proof works or not. They are simply interesting questions about the universe we live in.

I hope I’ve clearly summarised why P=NP would not necessarily be earth-shattering. Now let’s look at the other side:

What if P≠NP is true?

In other words, let us suppose that someone has written a paper that proves, to the satisfaction of nearly everyone, that P ≠ NP. There will always be some dissenters, as proofs are social interactions, but let us suppose a proof has been accepted by a majority of Gödel Prize winners, Richard Lipton has blogged about it favourably, Terence Tao and Timothy Gowers are satisfied, a paper is published in a top journal, the authors give invited talks at top conferences and are able to answer the questions that are raised (edit: including the a priori objections to any P ≠ NP proof that Scott Aaronson has helpfully raised), and the Clay Mathematics Institute has decided to make a Millennium Prize award.

Note my inclusion of two mathematicians in the list above. I think the techniques that will be used to separate P from NP (in other words, that will show that P differs from NP), will require us to deeply understand the structure of pseudo-random phenomena. So I expect involvement of the people who have laid some of the conceptual foundations and made some of the key insights into these questions. I expect they will have expert commentary on a proof, if they are not themselves part of the team proving it.

Most complexity theorists already assume P is not equal to NP (or at least they did a few years ago). In fact, many in complexity assume much more: for instance, that W[1] ≠ FPT (this is the driving assumption behind most work on parameterized complexity), that NP and co-NP differ (this is what makes work on proof complexity interesting), that GRAPH ISOMORPHISM can be solved in quasi-polynomial time but not in polynomial time (I’m not sure anyone actually believes this, but I have heard it bandied about), and so on. Each of these statements implies that P ≠ NP, but is not known to follow from it. By saying “a proof will require understanding pseudo-randomness”, I am implicitly making a stronger statement along the above lines.

What are the consequences? A separation result between P and NP would not say anything about cryptography, but the techniques developed for the proof might well have consequences for cryptography, as discussed by Russell Impagliazzo in A Personal View of Average-Case Complexity. Even if we are not living in Impagliazzo’s Heuristica or Pessiland, it is still possible that some current cryptosystems are easy to crack, since the problems on which some widely used cryptosystems are built are not known to be NP-complete, and in particular have not been rigorously proved to be hard to invert. RSA is based on multiplying together large prime numbers, and it seems difficult to factor them out again. Yet the decision version of factoring is not known to be NP-complete. (By the way, I disagree with Impagliazzo’s view of how Algorithmica would work; there seem to me to be several very different subuniverses possible in that scenario, as I discussed here.)

We could certainly deduce the separation of classes below P from classes above P. So we would know that that ~~ACC~~ AC^{0}[6]^{0}[6] differs from NEXPTIME (some people regard it as really embarrassing that this question remains open). But at this point I’m somewhat stumped, as all the examples that come to mind are just trivial consequences of existing inclusions. Yet the structure of the Complexity Zoo appears much more complicated, and I feel there must be other non-trivial relationships lurking. This leads to a question, which is really about the lattice structure of complexity classes.

If we knew that there existed problems in NP that cannot be solved in polynomial time, could we then deduce the separation of other complexity classes not in direct relationship to P or NP?

(Edit 20100814: added link to Scott Aaronson’s a priori objections.)

(Edit 20100816: fixed ACC^0 -> AC^0.)

I attended a talk this saturday by Prof. Narendra S. Chaudhari on a possible proof for P=NP. A polynomial time algorithm O(N^13) for solving the 3SAT problem. from various angles this seemed to be the answer for the famed problem. In this non-DFS approach the key issue seems to be the representation step that inherently avoids the exponential time complexity. Please check out the paper published in Indian Journal of Mathematics and Slides of the talk by this unassuming man at http://dcis.uohyd.ernet.in/~wankarcs//index_files/seminar.htm.

Very very exciting times when there are two serious attempts one by Deolalikar at P != NP and a constructive proof of Chaudhari for P=NP.

Comment by Raju Bapi — 30 August 2010 @ 17:11 |

Alas, I am not convinced by Professor Chaudhari’s approach. The main idea seems to be to reduce 3SAT to Horn-SAT, but this is less expressive.

Comment by András Salamon — 2 September 2010 @ 13:09 |