FOM: Re: FOM P=NP

[Martin Davis]

>
>This is completely misleading. The actual situation is absolutely perfect
>for a crucial mathematical problem. Almost nobody thinks that P=NP, and I
>think that if P=NP, then it is very likely that we misunderstand algorithms
>so much that the solution will have substantial practical consequences for
>algorithm design. 

..............................................................................

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

>P=NP is a deep conceptual problem as well as a technical problem. 

If indeed P \ne NP, then one would have to agree that deep conceptual issues
are involved. If it turns out the other way, many a dissertation in CS will
collapse along with the P-time hierarchy, but the problem itself will in
this case be seen as of little conceptual interest in itself.

Martin Davis