arvind@utcsri.UUCP (05/29/87)
Date: Mon 18 May EDT 1987 11:38
From: dsj%btl.csnet@relay.cs.net
Subject: An announcement and Two Proposals
Announcing the establishment of the
MALCOLM W. BROWNE MEMORIAL REPOSITORY
FOR PROOFS THAT P = NP (OR ITS NEGATION)
Given the recent flurry of papers and talks with provocative titles
like ``P = NP'' or ``P != NP,'' it now seems appropriate, if only for
sociological purposes, to establish a central clearing house for such
claims. To this end, Mike Garey and I announce the establishment of the
above repository, named after the reporter for the NY Times who was
responsible for the most widely disseminated ``proof'' that P = NP (in
his 1979 news article in which he illustrated the usefulness of
Khachian's new algorithm by claiming that it could be used to solve the
traveling salesman problem).
Those having purported resolutions to the P versus NP question are
urged to send a copy to me at the below address (and those finding holes
in the above are likewise urged to report). For historical purposes,
we are also interested in collecting information about retracted
claims from the past. (Our favorite is a supposedly polynomial-time
algorithm for SATISFIABILITY that made use of a new logic system based
on the Book of Genesis in the Old Testament.) We will of course honor
requests for anonymity by authors of such papers, as our main goal is to
gather information on the techniques used and approaches attempted, and
to look for trends. (Currently it seems that proofs that P = NP outnumber
proofs to the contrary by a ratio of over 4 to 1.)
Note that this Repository is just that, a repository, and we are
not offering a verification service to new claimants. (It would of course
be a conflict of interest for Mike or me to be involved in authenticating
claims, given our financial stake in the answer.) We will, however, stamp
each new proof with the date received, and thus may be of use in helping
you establish priority, should your proof be correct.
The question of verification raises serious issues. The flurry of
new ``proofs'' in the past year (I have seen or heard of six), espe-
cially the widely-publicized ones (you know who you are), have taken a
considerable toll on the research community. Not only has much time
been spent by industrious researchers attempting to verify the claims or
find the holes in the proofs, but the rest of us have wasted countless
hours gossiping about the supposed proofs and their authors, time that
could have been much more usefully spent gossiping about the traditional
topics, such as who is leaving which job to go where, and how many papers
were submitted to STOC.
A MODEST PROPOSAL
We thus modestly propose that anyone claiming a resolution to the
P versus NP question be required to post a $1,000 bond, refundable only
if the proof turns out to be correct. If the proof fails, the money
could be used to pay for the efforts of those reader(s) who found the
proof's fatal flaw. Actually, why not use only half the money to pay
the flaw-finders, and use the rest to help endow a prize. The bond could
then be viewed as an ``entry fee'' of $1,000 (in 1987 dollars, indexed to
inflation of course) for the P versus NP Contest. (Revisions of proofs
in which substantial errors had previously been found would of course be
treated as new submissions and hence require a second entry fee.)
You would still be perfectly free to make any claim you wanted to
without paying a fee. However, your failure to ``put your money
where your mouth is'' might well be taken to indicate a lack of confidence
in your proof, and thus could discourage would-be verifiers from taking
your claims seriously. Conversely, outsiders who might otherwise be
viewed as ``crackpots'' and ignored would now have a simple, albeit
expensive method for quickly gaining the attention of the theoretical
community. Now, admittedly, some may object that requiring a high entry
fee for our contest discriminates against impecunious students and residents
of countries with hard currency restrictions. However, any such person
with a valid resolution of the P versus NP question would most likely be
able to find financial backers. (There is of course the danger
that prospective backers might abscond with your result and claim it as
their own. Here is where the abovementioned Repository can play another
useful role: simply send a copy of your paper to the Repository first,
before approaching any potential backers.) Furthermore, one still retains
the traditional option of discreetly submitting one's proof for journal
publication, in which case the standard refereeing process can be relied
on to evaluate the credibility of the result for free, and with the quick
response time we have all come to know and love. There should be no
difficulty in raising the required fee once the paper has survived
refereeing and appeared in print.
AN ALTERNATIVE PROPOSAL
Despite the eminent reasonableness of the above proposal, we suspect
that the idea of a self-funding prize may still be a bit ahead of its
time. We believe, however, that the time is ripe for an award of some sort.
The P versus NP question has now been a subject of active interest for
over 20 years and is viewed by many as one of the most important open
problems in all of mathematics. We thus propose that SIGACT establish a
prize, say the ``ACM SIGACT ``P Versus NP'' Prize, to be awarded for the
resolution of the question of whether P = NP. Given SIGACT's currently
more-than-adequate reserves, the importance of the question, and the fact
that the Prize will hopefully only be awarded once, we suggest that the
amount of the prize be set at $10,000.
Comments on this proposal and how such a prize fund might be admin-
istered are welcome. I plan to raise the idea formally at the SIGACT
Business meeting during the STOC meeting later this month in New York
City.
David S. Johnson
Room 2D-150
AT&T Bell Laboratories
Murray Hill, NJ 07974