home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / math / 14911 < prev    next >
Encoding:
Internet Message Format  |  1992-11-13  |  1.3 KB
  1. Xref: sparky sci.math:14911 comp.theory:2407
  2. Newsgroups: sci.math,comp.theory
  3. Path: sparky!uunet!stanford.edu!CSD-NewsHost.Stanford.EDU!Sunburn.Stanford.EDU!pratt
  4. From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
  5. Subject: Re: NP Completeness Question
  6. Message-ID: <1992Nov13.154406.4800@CSD-NewsHost.Stanford.EDU>
  7. Sender: news@CSD-NewsHost.Stanford.EDU
  8. Organization: Computer Science Department,  Stanford University.
  9. References: <1dpkkeINNad2@mizar.usc.edu> <BxMu2J.2JD@watserv1.uwaterloo.ca>
  10. Date: Fri, 13 Nov 1992 15:44:06 GMT
  11. Lines: 14
  12.  
  13. In article <BxMu2J.2JD@watserv1.uwaterloo.ca> nrswart@phonon.uwaterloo.ca (Nicholas R. Swart) writes:
  14. >Professor E.R. Swart of the Computer Science Department at the University
  15. >of Guelph, has recently developed a polynomial-sized linear programing
  16. >formulation of the graph isomorphism problem and he has been able to show
  17. >that with minor modifications, this same formulation can be used to solve
  18. >the Hamilton tour, clique and other subgraph isomorphism problems.
  19.  
  20. Papadimitriou showed in 1975 an exponential lower bound on
  21. simplex-based solutions of the travelling salesman problem.  Since
  22. linear programming solves simplex problems (and indeed has polynomial
  23. time solutions), the above account renders the claim very unconvincing
  24. by making no mention of an additional trick.
  25. -- 
  26. Vaughan Pratt              A fallacy is worth a thousand steps.
  27.