Need article on P=NP

2 views
Skip to first unread message

B...@psuvm.bitnet

unread,
Mar 23, 1986, 10:23:31 PM3/23/86
to
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: B...@PSUVM.BITNET

Stephen C North

unread,
Mar 25, 1986, 5:20:57 PM3/25/86
to
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!

Gaston H Gonnet

unread,
Mar 26, 1986, 3:56:58 PM3/26/86
to
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.

j...@wucs.uucp

unread,
Mar 27, 1986, 5:34:52 PM3/27/86
to
In article <4626BSD@PSUVM> B...@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: j...@wucs.UUCP or ..!{ihnp4,seismo}!wucs!jst
ARPANET: wucs!j...@seismo.ARPA
CSNET: wucs!j...@seismo.ARPA%csnet-relay

Reply all
Reply to author
Forward
0 new messages