FOM: How likely is P = NP?
martind at cs.berkeley.edu
Sat Dec 20 18:17:09 EST 1997
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.
More information about the FOM