home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / math / 14922 < prev    next >
Encoding:
Internet Message Format  |  1992-11-14  |  2.2 KB
  1. Xref: sparky sci.math:14922 comp.theory:2412
  2. Newsgroups: sci.math,comp.theory
  3. Path: sparky!uunet!destroyer!gatech!hubcap!mjs
  4. From: mjs@hubcap.clemson.edu (M. J. Saltzman)
  5. Subject: Re: NP Completeness Question
  6. Message-ID: <1992Nov13.170538.14844@hubcap.clemson.edu>
  7. Organization: Clemson University, Clemson SC
  8. References: <1dpkkeINNad2@mizar.usc.edu> <BxMu2J.2JD@watserv1.uwaterloo.ca> <1992Nov13.154406.4800@CSD-NewsHost.Stanford.EDU>
  9. Date: Fri, 13 Nov 1992 17:05:38 GMT
  10. Lines: 37
  11.  
  12. In article <1992Nov13.154406.4800@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
  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. I don't understand your point.  The simplex method solves linear
  27. programs (but in exponential worst-case time).  On the other hand,
  28. linear programming is in P, as shown by Khachian (the ellipsoid
  29. method) and Karmarkar (interior point methods).
  30.  
  31. Furhtermore, although linear formulations of the TSP require an
  32. exponential number of constraints, that in itself is not enough to
  33. ensure that a problem is NP-hard.  The matching (edge cover) problem
  34. has an exponential number of constraints, yet it is solvable in
  35. polynomial time.
  36.  
  37. I found a reference to a 1978 paper by Papadimitriou (in Math
  38. Programming), which shows that determining if two tours represent
  39. adjacent vertices of the TSP polytope is itself NP-complete.  Is this
  40. the result you're thinking of?
  41.  
  42. >-- 
  43. >Vaughan Pratt              A fallacy is worth a thousand steps.
  44.  
  45. -- 
  46.         Matthew Saltzman
  47.         Clemson University Math Sciences
  48.         mjs@clemson.edu
  49.