Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!seismo!mcvax!hafro!krafla!snorri
From: snorri@krafla.UUCP (Snorri Agnarsson)
Newsgroups: comp.ai,sci.math.symbolic
Subject: Re: P may indeed = NP !!
Message-ID: <11@krafla.UUCP>
Date: Tue, 15-Sep-87 05:49:49 EDT
Article-I.D.: krafla.11
Posted: Tue Sep 15 05:49:49 1987
Date-Received: Fri, 18-Sep-87 04:16:51 EDT
References: <761@maccs.UUCP>
Organization: University of Iceland
Lines: 21
Keywords: polynomial time algorithms
Summary: Why Karmarkars polynomial LP algorithm does not prove that P=NP
Xref: mnetor comp.ai:777 sci.math.symbolic:154

...
> "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