Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!think!mit-eddie!genrad!decvax!ucbvax!cartan!brahms!desj
From: desj@brahms (David desJardins)
Newsgroups: sci.math
Subject: Re: P = NP
Message-ID: <419@cartan.Berkeley.EDU>
Date: Mon, 24-Nov-86 16:49:06 EST
Article-I.D.: cartan.419
Posted: Mon Nov 24 16:49:06 1986
Date-Received: Mon, 24-Nov-86 23:37:55 EST
References: <1953@emory.UUCP> <269@mipos3.UUCP> <8884@duke.duke.UUCP>
Sender: daemon@cartan.Berkeley.EDU
Reply-To: desj@brahms (David desJardins)
Distribution: na
Organization: Math Dept. UC Berkeley
Lines: 37
Keywords: P=NP, computability, 8-)

In article <8884@duke.duke.UUCP> ola@duke.UUCP (Owen L. Astrachan) writes:
>A small but productive and insightful group of graduate students here at
>Duke have discovered a wonderful proof that the question "P=NP?" is, in
>fact, computable.
>
>Unfortunately, the margins of our editor are too small to contain this
>marvelous proof.

   I have reread this a few times, and have finally concluded that it
must be meant as some sort of joke (the appearance of `Keywords: 8-)'
tends to confirm this impression).  The statement `P=NP? is computable'
can be interpreted in many ways, some of which are meaningful and some
of which are not.

   If Mr. Astrachan is joking, perhaps he means simply that if P=NP then
the question is computable by the machine which always returns YES, and
if P!=NP the question is computable by the machine which always returns
NO.  If he means this, then I suspect he is mistaken.  To prove this,
he must first prove that the question P=NP? is decidable, and this, I
suspect, is nearly as hard as solving the problem itself.  (Specifically,
a given Turing machine will produce the same output regardless of the
axioms of your set theory, while P=NP? could conceivably depend on those
axioms.)

   Now, if Mr. Astrachan was more serious, I might suppose that he meant,
"There is a specified computation of finite duration which will answer
the question."  This is a very meaningful statement, and it would not
surprise me at all if certain mathematical problems might one day be
"resolved" in this way before their truth or falsity is determined.
But the `8-)' makes me doubt that this is what Mr. Astrachan has done
(not to mention that I suspect I would have heard of it by now).

   -- David desJardins

P.S. I don't find this sort of `humor' particularly appropriate in
net.math.  Neither are "I want a preprint of P=NP" or (especially)
"Me Too!!!!!" of course, but at least we can simply ignore them.