FOM: P=NP

[Vaughan Pratt]

>From: martind at cs.berkeley.edu (Martin Davis)
>Date: Fri, 19 Dec 1997 11:08:47 -0800
>
>OK. Let me stick my neck out. I think the betting is 50-50 on P=NP.

>From: Stephen Cook <sacook at cs.toronto.edu>
>Date:   Fri, 19 Dec 1997 17:54:54 -0500
>
>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.

>From: martind at cs.berkeley.edu (Martin Davis)
>Date: Sat, 20 Dec 1997 15:17:09 -0800
>
>This [...] is a very serious argument.


I'd be interested in knowing whether Martin's even odds for strictness
of the middle inclusion also apply to strictness of the other two
inclusions.

FWIW, my own odds would be 3/1 against P=NP and 100/1 against each of
the other two equalities.  In 1975 I bet that P=NP with a couple of
people at even odds.  While I wouldn't offer quite those odds today,
neither would I bet 10/1 against P=NP.

As arguments lending some support for P=NP, note that this question
concerns the *time* complexity of *sequential* computation.  Changing
either time to space, *or* sequential to parallel, makes the equality
true (respectively Savitch 1970 and Pratt-Stockmeyer 1974).

But these analogies are not really all that strong, in that both these
demonstrated equalities have straightforward proofs that were found
over two decades ago.  Today it seems relatively unlikely that there
could be a comparably straightforward proof of P=NP, much as it seems
unlikely today that Fermat could have had a reasonably sized proof of
his last theorem.

As Steve points out, our understanding of lower bounds is still
primitive, and I feel we have somewhat less reason to doubt the
existence of a straightforward refutation of P=NP.  But even that
possibility is looking more remote these days, and the likely prospect
of a resolution of P=NP is that it will be a lengthy argument whichever
way it goes.

And if that's the case, I wouldn't give sixpence for anyone's intuition
that P=NP "has to be false", particularly given that it becomes true
under either of the above modifications.

The LOGSPACE=PTIME and NPTIME=PSPACE questions have not received as
much attention.  Furthermore I cannot think of any relevantly analogous
modifications of those questions rendering them true.  And finally we
know that one of the three equalities *is* false.  With these three
considerations, I would be utterly astonished by either LOGSPACE=PTIME
or NPTIME=PSPACE.  Were both to obtain (thereby resolving P=NP) I would
become a monk.

Vaughan Pratt