FOM: P=NP

[Martin Davis]

At 06:19 AM 12/20/97 +0100, Harvey Friedman wrote:
>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)?

You're not sticking your neck out at all. I find your numbers conservative.
But of course mathematical truth isn't established by majprity vote. [The
prevailing opinion among logicians before Matiyasevich was that Julia
Robinson's hypothesis asserting the existence of a Diophantine equation with
(in a sutiable sense) exponential growth was false. See Kreisel in MR
24(1962), p.573.]


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

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

Certainly. Steve Cook made an excellent point (see my previous posting) that
among a bunch of separation principles that have remained unporved, we know
that at least one must be true.

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

Taking the problem in this expanded sense, I certainly agree. The problem of
characterizing rigorously problems for which the best algorithms are what
the Russans call "brute force" and distinguishing them from the others is of
great importance. However, I still maintain that if it should turn out that
P=NP that fact in itself will come to seem an unimportant historical
footnote. It may also be that the almost universal belief that P \ne NP
stands in the way of the correct resolution of the problem.

Harvey, thanks for the kind words about my post. I have been enjoying yours
immensely (except when you hit people :-) ).

Martin