home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 4844 < prev    next >
Encoding:
Internet Message Format  |  1992-11-15  |  1.7 KB
  1. Xref: sparky sci.crypt:4844 sci.math:15015 comp.theory:2427
  2. Newsgroups: sci.crypt,sci.math,comp.theory
  3. Path: sparky!uunet!telebit!phr
  4. From: phr@telebit.com (Paul Rubin)
  5. Subject: Re: Cryptography and P=NP
  6. In-Reply-To: djimenez@ringer.cs.utsa.edu's message of Sun, 15 Nov 1992 11:09:45 GMT
  7. Message-ID: <PHR.92Nov15203840@napa.telebit.com>
  8. Sender: news@telebit.com
  9. Nntp-Posting-Host: napa.telebit.com
  10. Organization: Telebit Corporation; Sunnyvale, CA, USA
  11. References: <1992Nov15.110945.19939@ringer.cs.utsa.edu>
  12. Date: 15 Nov 92 20:38:40
  13. Lines: 22
  14.  
  15. >Professor E.R. Swart of the Computer Science Department at the University
  16. >of Guelph, has recently developed a polynomial-sized linear programing
  17. >formulation of the graph isomorphism problem and he has been able to show
  18. >that with minor modifications, this same formulation can be used to solve
  19. >the Hamilton tour, clique and other subgraph isomorphism problems.
  20.  
  21. Fortunately or unfortunately, Swart's stuff is like the "proofs"
  22. of Fermat's last theorem that turn up from time to time.  He
  23. first released his P=NP "proof" in the early 80's and has been
  24. trying to patch up the mistakes ever since.
  25.  
  26. Also, nobody has ever proved that graph isomorphism is NP-complete,
  27. unlike those other problems.  There is a clever argument by Goldwasser
  28. and Sipser from a few years ago that graph isomorphism is probably
  29. *not* NP-complete.  (I don't keep up with this field and don't
  30. know what's been happening since then.).
  31.  
  32. It is true that if P=NP then all cryptography everywhere (not just RSA)
  33. is dead; but at this point I wouldn't take Swart's claims seriously
  34. without seeing some consensus among complexity efforts that unlike
  35. his previous attempts, his latest effort is free of bugs.
  36.  
  37.