Why is proving P != NP so hard?

Question

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.

Answer 1

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.