FOM: P=NP ?

[Martin Davis]

Some time ago Steve Cook wrote me "off line". I think his message is of
general interest, and he has permitted me to post it which I do below. But
first:

At 03:52 PM 1/3/98 -0800, Vaughan Pratt wrote:
>
>>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.
..............................................
>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.
>

I think that the inclusion most likely to be proper is that between NP and
PSPACE. After all, the entire P-time hierarchy sits between them.

Martin
***********************************************************************
Now Steve's message:

>Martin,
>      I'll reply to your message off line, since I'm not sure how
>much general FOM interest there is in my first point.  Here is
>what I wrote:
>
>	 
>	 >
>	 >I doubt that the simplest polytime algorithm for SAT would have a run
>	ning
>	 >time like n^1000.  The theory of algorithms is a mature and sophistic
>	ated
>	 >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.
>	 
>And here is your comment:
>
>	 I just don't find anything coherent in this argument. I had proposed t
>	he
>	 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.
>
>Of course we have no experience with polynomial time algorithms for NP-complete
>problem since none is known.  So to guess what a polytime algorithm for SAT
>might look like we have no choice but to draw on our extensive experience with
>polytime algorithms from other domains.  
>
>To put it another way, if problems from other domains had polytime algorithms
>with huge exponents, then it would seem more plausible that this was the
case for
>SAT.   Therefore the lack of such examples  is evidence that there is none
for SAT.
>
>Steve
>