FOM: How likely is P = NP?

[Stephen Cook]

Martin Davis mentioned my name, so let me reply to his recent message
about the likelihood that P = NP.   
   Martin said
---------------------------------
OK. Let me stick my neck out. I think the betting is 50-50 on P=NP. The
heuristic evidence on the basis of which P \ne NP is so widely believed is
based on what I call the Cook-Karp thesis identifying P-time computability
with "feasible" computability. And the evidence for this is very weak
indeed. I am quite prepared to believe that there is no very good algorithm
for any of the myriad of NP-complete problems that have been produced, but I
know of no good reason to believe that there are no P-time algorithms for
them (say with asymptotic running time 10000(n^1000)). [When I put this to
Juris Hartmanis some years ago, he retorted that God would not be so cruel.]
--------------------------------------------

I doubt that the simplest polytime algorithm for SAT would have a running
time like n^1000.  The theory of algorithms is a mature and sophisticated
field, and has shown hundreds of natural problems to be in P.  If we
define the degree of a problem in P to be the least d such that the
problem can be solved in time O(n^d), then the largest degree natural
problem that I'm aware of is factoring polynomials over the rationals.
The original algorithm of Lenstra/Lenstra/Lovasz has a runtime of
something like O(n^12), but improvements have been found with
smaller exponents.  Of course if one pushes the word "natural" then
a higher degree example can be found.  But SAT is pretty natural.

Here is one argument that likely P not= NP:  The theory of algorithms is
much more highly developed and successful than the theory of lower
bounds.  As evidence of our inability to prove lower bounds, consider
the sequence of inclusions

   LOGSPACE  \subset   P   \subset   NP    \subset  PSPACE

We know that the first class is a proper subset of the last, so at least
one of the intermediate inclusions must be proper.  But we haven't been
able to prove any of them is proper.

In fact there is a great dearth of lower bound proofs for natural problems
in complexity theory.  This is in sharp contrast to the rich theory
available for showing problems are in P.

   Concerning what Martin calls the Cook-Karp thesis identifying P-time
computability with "feasible" computability, I would assert only a weaker
variation, namely P-time computability coincides with feasible computability
only for natural problems.  I argue this in my paper in Proc International
Congress of Mathematicians, 1990 (I Satake, ed).

Steve Cook