home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2810 < prev    next >
Encoding:
Internet Message Format  |  1993-01-06  |  1.2 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!att!allegra!alice!reeds
  2. From: reeds@alice.att.com (Jim Reeds)
  3. Newsgroups: comp.theory
  4. Subject: Re: P=NP; the proof
  5. Summary: Not!
  6. Keywords: Collapse of hierarchy
  7. Message-ID: <24563@alice.att.com>
  8. Date: 6 Jan 93 22:40:53 GMT
  9. Article-I.D.: alice.24563
  10. References: <1idr1nINNrl@nunki.anu.edu.au>
  11. Distribution: inet
  12. Organization: AT&T Bell Laboratories, Murray Hill NJ
  13. Lines: 20
  14.  
  15.  
  16.  
  17. Mike Robson writes
  18.  
  19. > Who can shoot down this alleged proof that P=NP?
  20.   [...]
  21. > Claim 2: If T is a solution to $LP$, it covers a permutation vector
  22. > $Q sub pi$.
  23.  
  24. Maybe I can.  The T matrix displayed in section 3 of Gismondi and Swart's
  25. isomorphism paper (sept 1992) covers no permutation vector.  (There
  26. are only 24, so you can check by brute force, if you want.)
  27.  
  28. Claim 2, if true, would imply that the feasible region for Robson's
  29. linear programming problem had precisely the set of permutation vectors
  30. as its extreme points.  This is clearly out of step with the discussion
  31. in G&S section 3.  I think G&S introduce their whole rigamarole of U vectors
  32. and actions of permutations on triples of symbols to get around this
  33. problem.
  34.  
  35.