kyukawa@watdragon.UUCP (Keitaro Yukawa) (11/29/86)
The following news appeared in the news group sci.math
--------------------------------------------------------------------
From hxd9622@ritcv.UUCP (Herman Darmawan) Fri Nov 28 02:41:59 1986
Newsgroups: sci.math
Subject: Re: P=NP (request for reference)
Date: 28 Nov 86 07:41:59 GMT
Reply-To: hxd9622@ritcv.UUCP (Herman Darmawan)
Organization: Rochester Institute of Technology, Rochester, NY
[]
P = NP
by
E. R. Swart
Department of Mathematics & Statistics
University of Guelph
Guelph, Ontario, Canada
Mathematical Series 1986-107
February 1986
Abstract:
A mathematical programming formulation of the Hamiltonian
circuit problem involving zero/one restrictions and triply subscripted
variables is presented and by relaxing the zero/one restrictions and
adding 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 Karmarkar concerning the existence of polynomial time
algorithms for linear programming this establishes the fact that the
Hamiltonian circuit problem can be solved in polynomial time. Since
the Hamiltonian circuit problem belongs to the set of NP-complete
problems it follows immediately that P=NP.
~40 pages.
-+-+-+-
Herman Darmawan @ Rochester Institute of Technology
UUCP {allegra,seismo}!rochester!ritcv!hxd9622
BITNET HND9622@RITVAXC
... fight mail hunger ... mail me now!jaw@aurora.UUCP (James A. Woods) (09/15/87)
# "The average mathematician should not forget that
intuition is the final authority." -- J. Barkley Rosser
"There's only one two." -- local TV station slogan
An informative synopsis of P=NP? here is surprising for those
accustomed to the usual style of general-purpose business periodicals.
One would expect something like this to appear in the more outre
New Scientist (hooray for British science writing!), where it might be
by-lined by John Maddox. But the enormity of the question, coupled
with its tight connection to operations research, makes it all
the more important that a general audience is exposed to the art.
The treatment comes complete with mention of revealing Cook/Karp/Levin
history, the role of random oracles, circuit complexity, and the solution
of the old Chomsky grammar chestnut by Neil Immerman. As they say in
the Southern states, "check it out" (of your local public library).
Also entertaining is Steven Johnson's plea for a halt to bogus P=NP
proofs, a cease fire perhaps encouraged by a monetary pot to contain a
$1000 bond for each submission posted before publication, which would then
be forfeited after a bug is found, and thence to the eventual prize
winner, Goedel notwithstanding. It's too bad that a team of "grunt
mathematicians" (*) must still filter the fluff.
Thoughts of anyone other than a Blum or a Karmarkar or a Matyasevich
or an Adelman coming through with a solution may be disturbing to some
workers in the field. Indeed, history has shown repeated lack of faith
with similar assaults [the Bieberbach Conjecture (De Branges), the Poincare
Conjecture (still unresolved), and Fermat's Last Theorem, where episodic
premature announcements in AMS Notices leave no one with even the hope that
a counterexample would fit on a T-shirt.]
As for P=NP, again, refer to the discussion in The Economist for
the week ending 4 September 1987.
-- James A. Woods (ames!jaw)
(*) Term first seen in the seminal paper by DeMillo, Lipton, and Perlis,
CACM, May 1979 -- "Social Processes and Proofs of Theorems and Programs",
well worth your attention for wry commentary and mathematics anecdotes.maiden@sdcsvax.UCSD.EDU (VLSI Layout Project) (09/15/87)
In article <1035@aurora.UUCP> jaw@aurora.UUCP (James A. Woods) writes: >Indeed, history has shown repeated lack of faith >with similar assaults [the Bieberbach Conjecture (De Branges), the Poincare >Conjecture (still unresolved), and Fermat's Last Theorem, where episodic ^^^^^^^^^^^^^^^^ Only unresolved in three dimensions. Resolved for all others.