Martin Davis on P vs NP, from the AMS Notices:
Notices: The outstanding problem in computer science now seems to be the P versus NP problem. Do you care to speculate on whether or how that will be resolved?
Davis: I have very unconventional views about that. It is taken for granted in the field that P and NP are different but that it's just much too hard for people to prove it. I think it's 50-50! I wouldn't be in the least astonished to find that P equals NP. I think the heuristic evidence that is given, when you look at it carefully, is just circular. I certainly agree that it's very unlikely that there are really good algorithms for NP-complete problems like satisfiability. But the equating of "good" with polynomial-time computability seems to me to lack evidence. People say "polynomial," but they mean with an exponent no higher than 3. I sort of see it as a reprise of the situation with Hilbert's Tenth Problem, where people didnt have any real imagination about what a polynomial with high degree could do. I was an invited speaker last summer at a meeting in Lisbon devoted to the satisfiability problem. In my talk I said that if I were a young person I would try to find a polynomial-time algorithm for satisfiability, not expecting it to be a particularly good algorithm!
Notices: Really!
Davis: Why not? I don't see any compelling reason there shouldnt be one.
Notices: But people aren't working on it from that point of view. People seem to think that P and NP are different.
Davis: Well, there is a million-dollar prize!
Notices: Is the question of whether there is a polynomial-time algorithm the correct way of measuring the difficulty of solving problems?
Davis: Well, that's really the question. Certainly theoretically the class of things for which there are polynomial-time algorithms has nice closure properties. So it's a mathematically attractive class. But the idea of identifying them with what's computationally feasible is I think the result of looking at an analogy with Church-Turing computability, which is a very successful formalization of the intuitive notion of what is calculable in principle when you don't think about resources. But it's just not a compelling analogy in my opinion.
[Here's the far too large PDF (283Mb)]
