home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / math / 14943 < prev    next >
Encoding:
Internet Message Format  |  1992-11-07  |  2.1 KB
  1. Xref: sparky sci.math:14943 comp.theory:2416
  2. Newsgroups: sci.math,comp.theory
  3. Path: sparky!uunet!charon.amdahl.com!pacbell.com!sgiblab!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!usenet.ins.cwru.edu!agate!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: <1992Nov14.023606.16319@CSD-NewsHost.Stanford.EDU>
  7. Sender: news@CSD-NewsHost.Stanford.EDU
  8. Organization: Computer Science Department,  Stanford University.
  9. References: <BxMu2J.2JD@watserv1.uwaterloo.ca> <1992Nov13.154406.4800@CSD-NewsHost.Stanford.EDU> <1992Nov13.170538.14844@hubcap.clemson.edu>
  10. Date: Sat, 14 Nov 1992 02:36:06 GMT
  11. Lines: 30
  12.  
  13. In article <1992Nov13.170538.14844@hubcap.clemson.edu> mjs@hubcap.clemson.edu (M. J. Saltzman) writes:
  14. >In article <1992Nov13.154406.4800@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
  15. >>Papadimitriou showed in 1975 an exponential lower bound on
  16. >>simplex-based solutions of the travelling salesman problem.  Since
  17. >>linear programming solves simplex problems (and indeed has polynomial
  18. >>time solutions), the above account renders the claim very unconvincing
  19. >>by making no mention of an additional trick.
  20. >
  21. >I don't understand your point.  The simplex method solves linear
  22. >programs (but in exponential worst-case time).
  23.  
  24. I cited a lower bound on a problem.  What does a lower bound on an
  25. algorithm have to do with this?
  26.  
  27. >Furhtermore, although linear formulations of the TSP require an
  28. >exponential number of constraints, that in itself is not enough to
  29. >ensure that a problem is NP-hard.
  30.  
  31. I said "exponential time lower bound."  If you have a justification for
  32. translating this to "NP-hard" then you're in an even better position
  33. than me to make my point that the proof must be wrong.
  34.  
  35. >I found a reference to a 1978 paper by Papadimitriou (in Math
  36. >Programming), which shows that determining if two tours represent
  37. >adjacent vertices of the TSP polytope is itself NP-complete.  Is this
  38. >the result you're thinking of?
  39.  
  40. See Yannakakis, STOC'88.
  41. -- 
  42. Vaughan Pratt              A fallacy is worth a thousand steps.
  43.