leb@maccs.UUCP (Anthony Hurst ) (09/12/87)
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).
Included here are three excerpts from the authoress Mary Dickieson.
She writes:
"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.
...
"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?
--
seismo!mnetor!{genat,lsuc}!maccs!leb Anthony Hurst
McMaster Dept. of Comp. Sci. & Systems (416)-525-9140 x4030
Will there be cigarettes in heaven?bs@faron.UUCP (Robert D. Silverman) (09/14/87)
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 Silvermanshafto@aurora.UUCP (Michael Shafto) (09/14/87)
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).
]
]"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.
]...
I recall a presentation I saw once at a high school science
fair in which the presentor drew three or four directed graphs
(or undirected, I guess) and announced that he had proved the
Four-Color Theorem. While it's true that many significant
breakthroughs have been initially treated as false alarms,
surely many more false alarms have been treated as false alarms.
Mike Shaftosnorri@krafla.UUCP (Snorri Agnarsson) (09/15/87)
... > "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." ... OK - let me take a guess as to what is wrong with this approach: My guess is that Karmarkars polynomial time algorithms are only polynomial time if calculations are performed using fixed accuracy floating point arithmetic, and if infinite precision arithmetic is used then the algorithms are no longer polynomial time. Furthermore, I would guess that to solve the Hamiltonian circuit problem you would need infinite precision arithmetic. -- Snorri Agnarsson UUCP: snorri@rhi.edu Science Istitute ...!mcvax!hafro!rhi!snorri University of Iceland
bs@linus.UUCP (09/17/87)
In article <11@krafla.UUCP] snorri@krafla.UUCP (Snorri Agnarsson) writes:
]...
]> "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."
]...
]
]
]OK - let me take a guess as to what is wrong with this approach:
]
]My guess is that Karmarkars polynomial time algorithms are only
]polynomial time if calculations are performed using fixed accuracy
]floating point arithmetic, and if infinite precision arithmetic is
]used then the algorithms are no longer polynomial time.
]Furthermore, I would guess that to solve the Hamiltonian circuit
]problem you would need infinite precision arithmetic.
]--
]Snorri Agnarsson UUCP: snorri@rhi.edu
]Science Istitute ...!mcvax!hafro!rhi!snorri
]University of Iceland
Sorry, your guess makes some sense but is incorrect. The arithmetic precision
required for Khachian's algorithm (and Karmarkar's) may be built into the
algorithm. Secondly, all linear programming problems with rational coefficients
may be solved using finite precision.
I'm getting tired of hearing about P=NP proofs. It reminds me too much of
the many crackpots from previous generations who tried to 'square the circle'
or 'trisect a general angle' with straightedge and compass. All of the P=NP
proofs reported so far have the same flaw: They try to formulate an NP problem
as a linear program but ALL wind up requiring an exponential number of
variables in the size of the problem instance.
Bob Silverman