Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!mit-eddie!necntc!linus!faron!bs
From: bs@faron.UUCP (Robert D. Silverman)
Newsgroups: comp.ai,sci.math.symbolic
Subject: Re: P may indeed = NP !!
Message-ID: <253@faron.UUCP>
Date: Mon, 14-Sep-87 08:25:56 EDT
Article-I.D.: faron.253
Posted: Mon Sep 14 08:25:56 1987
Date-Received: Tue, 15-Sep-87 05:39:09 EDT
References: <761@maccs.UUCP]
Reply-To: bs@faron.UUCP (Robert D. Silverman)
Organization: The MITRE Corporation, Bedford MA
Lines: 49
Keywords: polynomial time algorithms
Xref: mnetor comp.ai:765 sci.math.symbolic:149

In article <761@maccs.UUCP] leb@maccs.UUCP (Anthony (Tony) Hurst) writes:
]
]
]I normally do not keep track of mathematics papers, but I happened
]to notice an interesting news item that jumped right out at me.  It
]was reported in a recent issue of the University of Guelph's "Alumnus"
]magazine. (Guelph is in Ontario, Canada).
 
Obviously a highly reputable source :-) :-)

]
]"One of the most perplexing problems in computer science may have
]been solved by Professor Ted Swart, who has a joint appointment in
]the departments of Mathematics & Statistics and Computing & Infor-
]mation Science.  He has written a paper offering proof that P = NP.
]...
]
 
Noone, repeat noone who does serious research in computational complexity
really belives P=NP. I have seen several such 'proofs'. All are basically
the same: Some imaginative person formulates a problem in NP as a linear
program. Unfortunately, most of these people fail to realize that their
'formulation' requires a number of variables that is exponential in the
size of the problem. Poof goes the proof. 

I had already heard of Prof. Swart's purported proof and heard that it
suffers from the same defect.


]"Dr. Swart cautions that the jury is still out on whether his approach
]will be proved or disproved by his peers, but already his pronouncement
]has caused a stir in the computer world."
 
]...
]
]"Dr. Swart's problem establishes that the Hamilton circuit problem can
]be solved in polynomial time by converting a mathematical programming
]formulation of the problem into a linear programming formulation and
]using existing polynomial time algorithms as established by Kachiyan
]and Karmarkar."
]
]
]What I should like to know is, has Swart's paper "caused a stir in
]the computer world" and if not, why not?
 
See above. 


Bob Silverman