Article View: comp.theory
Article #1898Re: P=NP; the proof
From: Jim Reeds
Date: Wed, 06 Jan 1993 22:40
Date: Wed, 06 Jan 1993 22:40
19 lines
1226 bytes
1226 bytes
Mike Robson writes > Who can shoot down this alleged proof that P=NP? [...] > Claim 2: If T is a solution to $LP$, it covers a permutation vector > $Q sub pi$. Maybe I can. The T matrix displayed in section 3 of Gismondi and Swart's isomorphism paper (sept 1992) covers no permutation vector. (There are only 24, so you can check by brute force, if you want.) Claim 2, if true, would imply that the feasible region for Robson's linear programming problem had precisely the set of permutation vectors as its extreme points. This is clearly out of step with the discussion in G&S section 3. I think G&S introduce their whole rigamarole of U vectors and actions of permutations on triples of symbols to get around this problem.
Technical Details
Message-ID:
<24563@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>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: Not! Keywords: Collapse of hierarchy Message-ID: <24563@alice.att.com> Date: 6 Jan 93 22:40:53 GMT Article-I.D.: alice.24563 References: <1idr1nINNrl@nunki.anu.edu.au> Distribution: inet Organization: AT&T Bell Laboratories, Murray Hill NJ Lines: 20