Article View: comp.theory
Article #1905Re: P=NP; the proof
From: Jim Reeds
Date: Thu, 07 Jan 1993 16:00
Date: Thu, 07 Jan 1993 16:00
22 lines
1538 bytes
1538 bytes
jmr@cs.anu.edu.au (Mike Robson) writes: >[...] >I'll go back to trying to decide if the current Gismondi and Swart >linear programming formulation has the required property (that every >solution covers a permutation). If that claim is true, then I think >my approach is a good way to try and prove it. This is rather more than G&S themselves state. If every point in the feasible region covers a permutation, then the extreme points of the feasible region are exactly the permutations, and hence every point in the feasible region is expressible as a convex combination of permutations. But all G&S claim is that any solution is expresible as an affine combination of permutations, with AT MOST ONE NEGATIVE COEFFICIENT. (I would like to see a real proof that any solution is expressible as an affine combination of permutations, regardless of sign. Equivalently, I'd like to know the dimension of the affine hull of the G&S feasible region.) Jim
Technical Details
Message-ID:
<24567@alice.att.com>Path:
arc1-ca.pugleaf.net!sparky!uunet!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!att!allegra!alice!reedsReferences:
<1idr1nINNrl@nunki.anu.edu.au> <1ifcmpINN11k@nunki.anu.edu.au> <1ifljqINN137@nunki.anu.edu.au>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!sparky!uunet!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!att!allegra!alice!reeds From: reeds@alice.att.com (Jim Reeds) Newsgroups: comp.theory Subject: Re: P=NP; the proof Summary: Mike wants more than G&S claim! Keywords: Collapse of hierarchy Message-ID: <24567@alice.att.com> Date: 7 Jan 93 16:00:01 GMT Article-I.D.: alice.24567 References: <1idr1nINNrl@nunki.anu.edu.au> <1ifcmpINN11k@nunki.anu.edu.au> <1ifljqINN137@nunki.anu.edu.au> Distribution: inet Organization: AT&T Bell Laboratories, Murray Hill NJ Lines: 22