home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / math / 14912 < prev    next >
Encoding:
Internet Message Format  |  1992-11-13  |  1.3 KB
  1. Xref: sparky sci.math:14912 comp.theory:2408
  2. Newsgroups: sci.math,comp.theory
  3. Path: sparky!uunet!pipex!warwick!pavo.csi.cam.ac.uk!gjm11
  4. From: gjm11@cus.cam.ac.uk (G.J. McCaughan)
  5. Subject: Re: NP Completeness Question
  6. Message-ID: <1992Nov13.134642.25307@infodev.cam.ac.uk>
  7. Sender: news@infodev.cam.ac.uk (USENET news)
  8. Nntp-Posting-Host: apus.cus.cam.ac.uk
  9. Organization: U of Cambridge, England
  10. References: <1dpkkeINNad2@mizar.usc.edu> <BxMu2J.2JD@watserv1.uwaterloo.ca>
  11. Date: Fri, 13 Nov 1992 13:46:42 GMT
  12. Lines: 18
  13.  
  14. In article <BxMu2J.2JD@watserv1.uwaterloo.ca> nrswart@phonon.uwaterloo.ca (Nicholas R. Swart) writes:
  15.  
  16. >Professor E.R. Swart of the Computer Science Department at the University
  17. >of Guelph, has recently developed a polynomial-sized linear programing
  18. >formulation of the graph isomorphism problem and he has been able to show
  19. >that with minor modifications, this same formulation can be used to solve
  20. >the Hamilton tour, clique and other subgraph isomorphism problems.
  21. >
  22. >This proves that P=NP and all NP-complete and all other NP problems thus
  23. >have polynomial time algorithms.
  24. >
  25. >So to answer your question, 1 and 2 are probably both polynomial.
  26.  
  27. This *is* a joke, isn't it?
  28.  
  29. -- 
  30. Gareth McCaughan     Dept. of Pure Mathematics & Mathematical Statistics,
  31. gjm11@cus.cam.ac.uk  Cambridge University, England.    [Research student]
  32.