home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / 2405 < prev    next >
Encoding:
Internet Message Format  |  1992-11-13  |  1.9 KB
  1. Xref: sparky comp.theory:2405 sci.math:14910
  2. Path: sparky!uunet!ogicse!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!crabapple.srv.cs.cmu.edu!andrew.cmu.edu!br0w+
  3. From: br0w+@andrew.cmu.edu (Bruno W. Repetto)
  4. Newsgroups: comp.theory,sci.math
  5. Subject: Re: NP Completeness Question
  6. Message-ID: <sf0vZ=q00YUn8_95Ry@andrew.cmu.edu>
  7. Date: 13 Nov 92 04:18:51 GMT
  8. Article-I.D.: andrew.sf0vZ=q00YUn8_95Ry
  9. Organization: Doctoral student, Industrial Administration, Carnegie Mellon, Pittsburgh, PA
  10. Lines: 38
  11. In-Reply-To: <BxMu2J.2JD@watserv1.uwaterloo.ca>
  12.  
  13. Excerpts from netnews.comp.theory: 13-Nov-92 Re: NP Completeness
  14. Question by Nicholas R. Swart@phonon 
  15. .
  16. .
  17. .
  18. > Professor E.R. Swart of the Computer Science Department at the University
  19. > of Guelph, has recently developed a polynomial-sized linear programing
  20.                                       ^^^^^^^^^^^^^^^^ ^^^^^^
  21. > formulation of the graph isomorphism problem and he has been able to show
  22. > that with minor modifications, this same formulation can be used to solve
  23. > the Hamilton tour, clique and other subgraph isomorphism problems.
  24. >  
  25. > This proves that P=NP and all NP-complete and all other NP problems thus
  26. > have polynomial time algorithms.
  27. >  
  28. > So to answer your question, 1 and 2 are probably both polynomial.
  29. >  
  30. > Nicholas
  31. > Dept. of Elec. and Comp. Engineering
  32. > University of Waterloo
  33. > Waterloo, Ontario
  34. > CANADA
  35. > N2L 3G1
  36. .
  37. .
  38. .
  39.  
  40. The math programming model may be polynomial-sized, but it may still
  41. be a very difficult _integer_ program, and thus not linear.  This does
  42. not prove that P=NP.  It will, if it is also shown that the polyhedron
  43. defined by the formulation constraints has only integer vertices.
  44.  
  45. As Prof. Panayotis asks in a different message, could you provide
  46. the relevant reference for this?  Dr. Swart gave a proof that P=NP
  47. in '86 ('87?) that unfortunately turned out to be faulty.  Are you
  48. referring to this?
  49.  
  50. Bruno.  br0w+@andrew.cmu.edu
  51.