BSD@PSUVM.BITNET (03/24/86)
I'm looking for an article that was posted about 3 weeks or so
ago about some research being done by Ted Swart at the
University of Guelph. The article is about a linear programming
formulation of the Hamiltonian circuit problem showing
that P=NP.
Any help or pointers would we greatly appreciated.
-------
--Scott Dickson
Bitnet: BSD@PSUVM.BITNET
north@down.FUN (Stephen C North) (03/26/86)
P=NP? That one was knocked off at least three weeks ago in net.math and net.research by one Palith Balakrishnabati [1]. He used a result due his advisor, N. Karmarkar. The same Karmarkar that snagged the very big LP result. Balakrishnabati's result is a real tour de force. It combines algebraic geometry, Boyce-Codd normal form, probabilistic number theory, differential topology, and theoretical CAD/CAM. [1] Balakrishnabati, P. Private communication with Honey Danber. -- Parturiunt montes, nascetur ridiculus mus!
ghgonnet@watdaisy.UUCP (Gaston H Gonnet) (03/26/86)
Transcribed without comment (I have the technical report). Title: P = NP by E.R. Swart, Department of Computing and Information Science, University of Guelph, Research Report CIS86-02, February 1986. Abstract: A mathematical progamming formulation of the Hamilton circuit problem involving zero/one restrictions and triply subscripted variables is presented and by relaxing the zero/one restrictions and adding additional linear constraints together with additional variables, with up to as many as 8 subscripts, this formulation is converted into a linear programming formulation. In the light of the results of Kachiyan and Karmakar concerning the existence of polynomial time algorithms for linear programming this establishes the fact that the Hamilton circuit problem can be solved in polynomial time. Since the Hamilton circuit problem belongs to the set of NP-complete problems it follows that P = NP.
jst@wucs.UUCP (03/28/86)
In article <4626BSD@PSUVM> BSD@PSUVM.BITNET writes: >I'm looking for an article that was posted about 3 weeks or so >ago about some research being done by Ted Swart at the >University of Guelph. The article is about a linear programming >formulation of the Hamiltonian circuit problem showing >that P=NP. > Is this for real? It's still a few days early for April Fools day. If anyone has any definite information on this, please forward it to me. -- Jon Turner Washington University in St. Louis 314-889-6193 UUCP: jst@wucs.UUCP or ..!{ihnp4,seismo}!wucs!jst ARPANET: wucs!jst@seismo.ARPA CSNET: wucs!jst@seismo.ARPA%csnet-relay