Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!husc6!linus!bs
From: bs@linus.UUCP
Newsgroups: comp.ai,sci.math.symbolic
Subject: Re: P may indeed = NP !!
Message-ID: <13375@linus.UUCP>
Date: Wed, 16-Sep-87 23:02:38 EDT
Article-I.D.: linus.13375
Posted: Wed Sep 16 23:02:38 1987
Date-Received: Sat, 19-Sep-87 06:38:58 EDT
References: <761@maccs.UUCP] <11@krafla.UUCP>
Reply-To: bs@linus.UUCP (Robert D. Silverman)
Organization: The MITRE Corporation, Bedford MA
Lines: 36
Keywords: polynomial time algorithms
Xref: utgpu comp.ai:740 sci.math.symbolic:145

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