cmb@emory.UUCP (Chang Bang) (11/19/86)
I heard a rumor that somebody in the west coast proved P = NP. I would like to get a preprint of the proof or any information for the rumor.
majka@ubc-vision.UUCP (Marc Majka) (11/21/86)
In article <1953@emory.UUCP> cmb@emory.UUCP (Chang Bang) writes: > I heard a rumor that somebody in the west coast proved P = NP. I would > like to get a preprint of the proof or any information for the rumor. Yeah, I proved it a couple of days ago. I discovered the proof in a flash of insight while I was in the second floor washroom. I wrote the proof out on the wall. Unfortunately, by the time I came back with a pencil and paper to copy it down, Physical Plant had re-painted the place. Now I can't remember how the proof went.
ekwok@mipos3.UUCP (Edward C. Kwok) (11/21/86)
In article <1953@emory.UUCP> cmb@emory.UUCP (Chang Bang) writes: >I heard a rumor that somebody in the west coast proved >P = NP. I would like to get a preprint of the proof or >any information for the rumor. Me too!!!!!!!!!!!!!!!!!!!!
lieman@brahms.UUCP (11/22/86)
Sounds to me like you heard about Manuel Blum's recent results in the area of zero information proofs. For example, he examines the question of whether I can convince you that I have proved a certain result, without telling you anything about the result. He claims that this is possible. This result has great bearing on P = NP, but I don't believe it solves it. It might be best if you sent him a note, and asked him to post a summary to an appropriate newsgroup. He's a nice guy; he should oblige. He's at: blum@ernie.berkeley.edu ...ucbvax!ernie!blum (I think) Hope this helps. Daniel Lieman lieman@brahms.berkeley.edu
litow@uwmeecs.UUCP (11/23/86)
> Sounds to me like you heard about Manuel Blum's recent results in the > area of zero information proofs. For example, he examines the question > of whether I can convince you that I have proved a certain result, without > telling you anything about the result. He claims that this is possible. > > This result has great bearing on P = NP, but I don't believe it solves it. > It might be best if you sent him a note, and asked him to post a summary > to an appropriate newsgroup. He's a nice guy; he should oblige. He's > at: > blum@ernie.berkeley.edu > ...ucbvax!ernie!blum (I think) > > Hope this helps. > > Daniel Lieman > lieman@brahms.berkeley.edu A tech abstract appears in Math. Found. of CS 1986 springer lncs 233,pp 639- 650 by O. Goldreich, S. Micali and A. Wigderson whose work grows out of Blum's. *** REPLACE THIS LINE WITH YOUR MESSAGE ***
badri@ur-valhalla.UUCP (11/24/86)
In article <403@cartan.Berkeley.EDU> lieman@brahms (Dan Lieman) writes: >Sounds to me like you heard about Manuel Blum's recent results in the >area of zero information proofs. For example, he examines the question >of whether I can convince you that I have proved a certain result, without >telling you anything about the result. He claims that this is possible. > Is this statement supposed to be a joke or something? I cannot make any sense out of it. What exactly is meant by "without telling you anything about the result"? The moment you say that you have proved a certain result, you have disclosed the result. This would automatically contradict the second part of the statement. I would indeed like to hear more about this in sci.math. Badri Lokanathan -- "We will fight for the right to be free/\ ur-valhalla!badri@rochester.arpa We will build our own society //\\ {caip,cmcl2,columbia,cornell, We will - we will sing ///\\\ harvard,ll-xn,nike,rutgers,seismo, We will sing our own song." -UB40 ////\\\\ topaz}!rochester!ur-valhalla!badri
ola@duke.UUCP (Owen L. Astrachan) (11/24/86)
In article <269@mipos3.UUCP> ekwok@mipos3.UUCP (Edward C. Kwok) writes: >In article <1953@emory.UUCP> cmb@emory.UUCP (Chang Bang) writes: >>I heard a rumor that somebody in the west coast proved >>P = NP. I would like to get a preprint of the proof or >>any information for the rumor. > >Me too!!!!!!!!!!!!!!!!!!!! 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. Before requesting a "preprint" via email please be sure that you understand exactly what is being proved here. I would like to mention the co-authors (and fellow travellers) Albert Nigrin and Paul Lanzkron who helped simplify the proof considerably. -- Owen L. Astrachan, Dept.of Computer Science, Duke University, Durham NC 27706 Phone (919)684-5110 Ext. 29 CSNET: ola@duke UUCP: {ihnp4!decvax}!duke!ola ARPA: ola%duke@csnet-relay
rgatkinson@watmum.UUCP (11/24/86)
I was waiting for someone else to say this, but... Earlier this year, Ted Swartz (sp?) of the University of Guelph in Guelph, Ontario claimed to have a proof that P=NP. From what I know, the jury is still out on whether he is correct or not; his proof apparently can at best be called a (very long!) sketch. Some professors here at Waterloo that I have talked to doubt whether his proof is correct, but no one has yet been able to find an actual hole. I guess we just wait and see. -bob atkinson -- -bob atkinson "I do not think, therefore I am a moustache." - J.P. Sartre
leichter@yale.UUCP (Jerry Leichter) (11/24/86)
Badri Lockanathan expresses skepticism at the notion of a "zero knowledge
proof". Nevertheless, the references to this notion are real and valid;
there's a lot of very clever, hard work behind it all.
The intuitive idea is fairly simple; you should look at the actual papers for
the technical details.
Consider a predicate P. A zero-knowledge proof for P can be looked at as
an oracle that answers various questions with yes/no answers; the answers,
taken together, can be used to prove that P is true. The proof is zero-
knowledge if, given a pair of Turing machines S and T, where S can call the
oracle with a polynomial number of questions, and T can call on another oracle
that answers only one question: Is P true? (which it answers YES), then T
and S can write down proofs for exactly the same set of formulas.
The FROM of the predicates that one is concerned with might be exemplified
by: P = {N is a product of exactly two primes}. (Don't take this as a
LITERAL example!) A zero-knowledge proof of P would convince you that it
was true, but would not provide you with ANY information that would help
you factor N. That is: If you could factor N given such a proof, then you
could have simply started with the assumption that N was of this form and,
if that assumption happened to be true, factored just as easily.
-- Jerrygreg@endor.harvard.edu (Greg) (11/24/86)
In article <863@ur-valhalla.UUCP> badri@ur-valhalla.UUCP (Badri Lokanathan) writes: >In article <403@cartan.Berkeley.EDU> lieman@brahms (Dan Lieman) writes: >>Sounds to me like you heard about Manuel Blum's recent results in the >>area of zero information proofs. For example, he examines the question >>of whether I can convince you that I have proved a certain result, without >>telling you anything about the result. He claims that this is possible. >What exactly is meant by "without telling you anything about the >result"? The moment you say that you have proved a certain result, >you have disclosed the result. What Blum means is that he can convince you that he has proved a given theorem without telling you the proof of the theorem. Of course both of you know the statement of the theorem. Admittedly Blum's results are surprising, but they are not nonsensical. ---- Greg
firth@sei.cmu.edu (Robert Firth) (11/24/86)
In article <1953@emory.UUCP> cmb@emory.UUCP (Chang Bang) writes: > I heard a rumor that somebody in the west coast proved P = NP. I would > like to get a preprint of the proof or any information for the rumor. Your average Prolog interpreter should have no trouble generating a proof of this. Try, for instance All invisible dogs are dogs All dogs are visible --------------------------- All invisible dogs are visible
desj@brahms (David desJardins) (11/25/86)
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.
vassos@utcsri.UUCP (Vassos Hadzilacos) (11/25/86)
>>[...] For example, he examines the question >>of whether I can convince you that I have proved a certain result, without >>telling you anything about the result. He claims that this is possible. > Is this statement supposed to be a joke or something? I cannot make > any sense out of it. > What exactly is meant by "without telling you anything about the > result"? The moment you say that you have proved a certain result, > you have disclosed the result. This would automatically contradict the > second part of the statement. I would indeed like to hear more about > this in sci.math. > > Badri Lokanathan Example: Being able to convince you that a number is composite without telling you any of its prime factors would be a "0-information `proof'" that the number is non-prime. "Convincing you" basically amounts to you asking me questions that I must answer and which you've chosen so that if I answer by guessing (i.e. without really knowing what I am talking about) then with very high likelihood you'll figure out I am a fraud. Vassos Hadzilacos.