30
$\begingroup$

Does anyone have any insight into why it is so hard to prove that P != NP conjecture? There seems to be so much evidence in its favor, and so many problems and techniques with which to attack it, that I don't get why it has remained unproven for so long.

$\endgroup$
4
  • 1
    $\begingroup$ There are lots of good references at the Wikipedia article. You can probably also find some good discussions on many CS blogs, e.g. Fortnow's blog, Aaronson's blog, Lipton's blog... $\endgroup$ Jul 26, 2010 at 7:40
  • 12
    $\begingroup$ Does "so hard" mean "NP hard"?! :-) $\endgroup$ Jul 26, 2010 at 7:43
  • 2
    $\begingroup$ Scott Aaronson wrote about the algebrization barrier, and also reviews the other main obstacles. scottaaronson.com/papers/alg.pdf $\endgroup$ Jul 26, 2010 at 9:40
  • 1
    $\begingroup$ @Wadim: I strongly suspect (though some differ!) that resolving the P vs. NP problem is in $\text{NC}^0$. ;) $\endgroup$
    – Charles
    Jul 26, 2010 at 17:14

1 Answer 1

33
$\begingroup$

On the contrary, there are two major results in complexity theory that rule out a wide class of methods to show that $P \ne NP$. The first is the theorem of Baker, Gill, and Solovay, that a proof that $P \ne NP$ (or a proof that they are equal) cannot relativize. In other words, they showed that there exists an oracle relative to which they are equal, and an oracle relative to which they are different. The second result is the theorem of Razborov and Rudich, that if a widely accepted refinement of the $P \ne NP$ conjecture is true, then there does not exist a "natural proof" that they are different. By a natural proof, they mean a proof from a large class of combinatorial constructions. In light of those two theorems, there actually aren't very many known promising techniques left, even though there is a lot of evidence by example that the conjecture seems to be true. As Razborov and Rudich explain, these two results rule out candidate approaches to P vs NP for sort-of opposite reasons.

There is a CS professor named Ketan Mulmuley who has expressed some optimism that P vs NP can be solved with "geometric complexity theory". I can believe that Mulmuley is doing interesting work of some kind (which seems to involve quantum algebra and representation theory), but I haven't heard of many complexity theorists who are optimistic along with him that he can really solve P vs NP. (But hey, Perelman surprised everyone with a proof of the Poincare conjecture, so who knows.)


Some additional remarks. First, there are plenty of conjectures have ample evidence yet are difficult for no obvious reason. The P vs NP problem has an unusual status in that people have thought of rigorous reasons that it's hard.

Second, when people prove a "barrier result" (meaning, a negative result about how not to prove a conjecture), obviously the community will take it as a challenge to find new ideas that circumvent the barrier. As mentioned in the comments, there was even a conference last year on doing exactly that! Baker, Gill, and Solovay was published in 1975, and it took about 15 years to find convincing exceptions to their point about relativization. (Unconvincing exceptions that can be explained as unfairly restricted oracle access came more quickly.) Nonetheless, when I did a computer-assisted survey of binary relations between complexity classes a few years ago, it was clear that the vast majority of these proven relations still relativize. It is true that by now the research focus is on non-relativizing results, with the exception of quantum complexity classes, where relativizing results are still popular.

Third, the newer Razborov-Rudich theorem made people start all over again to look for barrier loopholes. Moreover the Baker-Gill-Solovay theorem, as an obstruction to P vs NP, was sharpened somewhat by Aaronson and Wigderson in their paper on "algebrization" of complexity class relations. My third point is that I can't speak with any authority on efforts to overcome the current set of barriers.

$\endgroup$
5
  • 3
    $\begingroup$ Gowers posted a long and carefully constructed dialogue about attempts to overcome the Razborov-Rudich obstacles, beginning here: gowers.wordpress.com/2009/09/22/… $\endgroup$ Jul 26, 2010 at 9:35
  • 1
    $\begingroup$ I seem to recall that Mulmuley has gone on record as estimating that his approach will take 100 years if successful. $\endgroup$ Jul 26, 2010 at 12:18
  • 2
    $\begingroup$ I think we should also mention two recent results: Timothy Chow had a paper on "almost natural proofs", basically saying that if one relaxes the largeness condition a little bit, then natural proofs do exist provably. Also Eric Allender and Michal Koucký have a paper named "Amplifying lower bounds by means of self-reducibility" Razbarov mentioned them in his talk in the first Barriers Workshop. intractability.princeton.edu/barriers-workshop $\endgroup$
    – Kaveh
    Jul 26, 2010 at 13:12
  • $\begingroup$ The Chow paper is, presumably, arxiv.org/abs/0805.1385 . $\endgroup$
    – Charles
    Jul 26, 2010 at 17:16
  • 1
    $\begingroup$ Another related paper: Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, "An axiomatic approach to algebrization", STOC 2009 $\endgroup$
    – Kaveh
    Aug 4, 2010 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.