FOM: How likely is P = NP?

[Martin Davis]

At 05:54 PM 12/19/97 -0500, Stephen Cook wrote:

>
>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.

I just don't find anything coherent in this argument. I had proposed the
possibility that NP-complete problems have P-time algorithms but with very
large exponents. I don't see how are experience with non NP-complete
problems is relevant.

>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.
>

This on the other hand is a very serious argument. Of course lower bounds
being hard to establish doesn't show they exist. 

Martin