FOM: P=NP

[Harvey Friedman]

This is a reply to Martin Davis, 11:08AM 12/19/97.

>OK. Let me stick my neck out. I think the betting is 50-50 on P=NP.

Not to the people I talk to. Has there been any survey of opinion on this
matter? It would be quite interesting to conduct such a survey in the
computer science community. And it would be a lot easier to conduct such a
survey on P=NP than on the continuum hypothesis - as Neil surely knows by
now.

I'll stick my neck out. The survey will show at least 95% notP=NP among
theoretical computer scientists. And at least 90% among academic computer
scientists as a whole. Why don't you embarrass me by citing an existing
survey or conducting one (off the fom of course)?

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

>From the asymptotic viewpoint, identifying P-time with "feasible" is a very
sensible first pass. Since our ignorance is so extreme, we don't really
need any second, third, etcetera passes at the moment.

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

This illustrates what is so great about this problem. It's the flexibility.
Suppose you are right - that there is no "very good algorithm" for the
myriad of NP-complete problems. And someone shows that there is a
polynomial time algorithm for them with ridiculous exponents and
coefficients. Then the problem takes on the altered form of, e.g.: is there
a quadratic algorithm for (most of) the myriad of NP-complete problems?
Then this problem assumes the same importance as the original problem.

Of course, one can get prematurely fussy at this stage, and worry about the
realism surrounding all asymptotic algorithms. But then finite model
complexity kicks in. The problem survives practically no matter what
happens!! Everytime there is a surprise in the = direction - there hasn't
been any real surprise yet - there is a corresponding adjustment to the
problem that takes over. Surely from this point of view, Martin, you will
agree that there will be crucially important negative results - eventually?

By the way, Lou - as you might have heard, Michael Freedman of Poincare
conjecture fame, has decided to move to Microsoft and work on P=NP. Have
you considered contacting him to find out some of the considerations in his
change of research direction, in order to test out some of your ideas (that
I have pretty much called plain old stubborn)?

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

In light of the point that I am making - the inexhaustable adjustments of
the P=NP question - your conclusion would be unwarranted. Agreed?

Thank you for your help in keeping the fom at an interesting, timely,
useful, and professional level.