home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2824 < prev    next >
Encoding:
Internet Message Format  |  1993-01-08  |  2.2 KB
  1. Path: sparky!uunet!munnari.oz.au!manuel.anu.edu.au!dubhe.anu.edu.au!nunki.anu.edu.au!not-for-mail
  2. From: jmr@cs.anu.edu.au (Mike Robson)
  3. Newsgroups: comp.theory
  4. Subject: Re: P=NP; the proof
  5. Date: 8 Jan 1993 16:22:40 +1100
  6. Organization: Computer Science Department, ANU, Australia
  7. Lines: 42
  8. Distribution: inet
  9. Message-ID: <1ij330INN2h8@nunki.anu.edu.au>
  10. References: <1idr1nINNrl@nunki.anu.edu.au> <1ifcmpINN11k@nunki.anu.edu.au> <1ifljqINN137@nunki.anu.edu.au> <24567@alice.att.com>
  11. NNTP-Posting-Host: nunki.anu.edu.au
  12. Keywords: Collapse of hierarchy
  13.  
  14. reeds@alice.att.com (Jim Reeds) writes:
  15.  
  16.  
  17.  
  18. >jmr@cs.anu.edu.au (Mike Robson) writes:
  19.  
  20. >>[...]
  21. >>I'll go back to trying to decide if the current Gismondi and Swart
  22. >>linear programming formulation has the required property (that every
  23. >>solution covers a permutation). If that claim is true, then I think
  24. >>my approach is a good way to try and prove it.
  25.  
  26. >This is rather more than G&S themselves state.  If every point in the
  27. >feasible region covers a permutation, then the extreme points of the
  28. >feasible region are exactly the permutations, and hence every point in
  29. >the feasible region is expressible as a convex combination of permutations.
  30.  
  31. I should have been more precise. I think they are claiming that every
  32. solution has covers the s and t variables of a permutation (not the u).
  33. I think that gets round your argument; if not things look bad.
  34.  
  35. >But all G&S claim is that any solution is expresible as an affine
  36. >combination of permutations, with AT MOST ONE NEGATIVE COEFFICIENT.
  37.  
  38. Where did they claim that?
  39.  
  40. >(I would like to see a real proof that any solution is expressible
  41. >as an affine combination of permutations, regardless of sign.  Equivalently,
  42. >I'd like to know the dimension of the affine hull of the G&S feasible
  43. >region.)
  44.  
  45. They claim to have a complete proof based on the dimensions of the spaces
  46. involved but I haven't seen any details.
  47. I have an idea of how to construct a proof by taking an arbitrary
  48. solution and systematically zeroing out all u variables except those
  49. of the identity permutation vector. This can be done by subtracting
  50. carefully chosen permutations, possibly preceded by adding other
  51. permutations which don't involve any u variables except the ones
  52. which you haven't got round to yet.
  53. >Jim
  54.  
  55. Mike.
  56.