home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2818 < prev    next >
Encoding:
Internet Message Format  |  1993-01-07  |  1.5 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: Mike wants more than G&S claim!
  6. Keywords: Collapse of hierarchy
  7. Message-ID: <24567@alice.att.com>
  8. Date: 7 Jan 93 16:00:01 GMT
  9. Article-I.D.: alice.24567
  10. References: <1idr1nINNrl@nunki.anu.edu.au> <1ifcmpINN11k@nunki.anu.edu.au> <1ifljqINN137@nunki.anu.edu.au>
  11. Distribution: inet
  12. Organization: AT&T Bell Laboratories, Murray Hill NJ
  13. Lines: 22
  14.  
  15.  
  16.  
  17. jmr@cs.anu.edu.au (Mike Robson) writes:
  18.  
  19. >[...]
  20. >I'll go back to trying to decide if the current Gismondi and Swart
  21. >linear programming formulation has the required property (that every
  22. >solution covers a permutation). If that claim is true, then I think
  23. >my approach is a good way to try and prove it.
  24.  
  25. This is rather more than G&S themselves state.  If every point in the
  26. feasible region covers a permutation, then the extreme points of the
  27. feasible region are exactly the permutations, and hence every point in
  28. the feasible region is expressible as a convex combination of permutations.
  29.  
  30. But all G&S claim is that any solution is expresible as an affine
  31. combination of permutations, with AT MOST ONE NEGATIVE COEFFICIENT.
  32. (I would like to see a real proof that any solution is expressible
  33. as an affine combination of permutations, regardless of sign.  Equivalently,
  34. I'd like to know the dimension of the affine hull of the G&S feasible
  35. region.)
  36. Jim
  37.