🚀 go-pugleaf

RetroBBS NetNews Server

Inspired by RockSolid Light RIP Retro Guy

Article View: comp.theory
Article #1898

Re: P=NP; the proof

#1898
From: Jim Reeds
Date: Wed, 06 Jan 1993 22:40
19 lines
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!reeds
References: <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