home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / theory / 2516 < prev    next >
Encoding:
Text File  |  1992-11-23  |  3.1 KB  |  66 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!news.smith.edu!orourke
  3. From: orourke@sophia.smith.edu (Joseph O'Rourke)
  4. Subject: Re: Silence on P=NP
  5. Message-ID: <1992Nov23.193912.9159@sophia.smith.edu>
  6. Organization: Smith College, Northampton, MA, US
  7. References: <1992Nov21.222755.18863@sophia.smith.edu> <1992Nov23.091136.7123@fwi.uva.nl> <By6nDC.6Gp@dcs.ed.ac.uk>
  8. Date: Mon, 23 Nov 1992 19:39:12 GMT
  9. Lines: 55
  10.  
  11. I received this reply to my posting from David Shallcross at Bellcore:
  12.  
  13. From davids@bellcore.com Mon Nov 23 12:44:35 1992
  14. Date: Mon, 23 Nov 92 12:43:17 -0500
  15. From: davids@bellcore.com (David Shallcross)
  16.  
  17. Subject: Re: Silence on P=NP
  18. Newsgroups: comp.theory
  19. In-Reply-To: <1992Nov21.222755.18863@sophia.smith.edu>
  20. Organization: Bellcore, Morristown NJ
  21.  
  22. In article <1992Nov21.222755.18863@sophia.smith.edu> you write:
  23. >The silence on the Swart & Gismondi proof of P=NP is deafening.
  24. >Will no one venture an opinion?  My knowledge of linear programming
  25. >is insufficient to the task.
  26.  
  27. Well, I have problems posting from here, but I read through the papers,
  28. and found some fundamental errors.  Basically, he works with the set
  29. of two-sided permutation operators on matrices f(X) = P'XP, where P
  30. is some permutation matrix and P' is the transpose of P.  Since f is
  31. linear in X, we can write this as f(x) = Tx, where x is just X
  32. rearranged into a vector.  He further rearranges T into a vector t, and
  33. (the usually combinatorial optimization - integer programming thing)
  34. gives a system F1 of linear inequalities such that the set of such t's
  35. is the set of integer vectors that satisfy F1.  (Let C1 be the set of
  36. real vectors that satisfy F1.(Gismondi and Swart never actually define
  37. C1.)) What we would like, in order to easily solve lots of NP-hard problems, 
  38. is a polynomial description of the convex hull C0 of such t's.  What they do, 
  39. up to some gaps in their proofs that I cannot quite follow, is give a set C2,
  40. containing C0 and contained in C1, by adding new variables, deducing
  41. new constraints, and projecting the new variables back out.
  42.  
  43. Their main theorem, which might be correct, is that any point in C2
  44. either lies in C0, or is a convex combination of a point in C1 and a
  45. point in C0.  This is not very surprising, because, for any set A0
  46. contained in any other set A1 (in R^n), the union of A0 with the
  47. interior of A1 also has this property.
  48.  
  49. The proof of Corollary 1 is clearly invalid, however.  It claims that
  50. if we intersect C2 with some additional linear constraints (that a
  51. graph Ga is mapped to a graph Gb by f) to get C3, and C3 is nonempty, 
  52. then C3 must contain an integer point (and so there must an isomorphism 
  53. between Ga and Gb).  The argument for this is that any point in C3 is the 
  54. convex combination of an integer point in C0 and some other point in C1, 
  55. which is true, but there is no reason that either of those two points
  56. need also satisfy the added linear constraints.
  57.  
  58. The later two papers more or less act as if C0=C2, in which case all
  59. their wonderous results would be true.  Basically, there are
  60. misunderstandings of the theory of integer programming.
  61.  
  62. Post this if you like.
  63.  
  64. Your once-student,
  65. David Shallcross
  66.