Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!watmath!clyde!burl!ulysses!gamma!epsilon!zeta!sabre!petrus!bellcore!decvax!decwrl!pyramid!pesnta!amd!amdcad!lll-crg!topaz!uwvax!pruhs From: pruhs@uwvax.UUCP (Kirk Pruhs) Newsgroups: net.math Subject: P = NP Article Message-ID: <729@uwvax.UUCP> Date: Tue, 25-Mar-86 13:11:18 EST Article-I.D.: uwvax.729 Posted: Tue Mar 25 13:11:18 1986 Date-Received: Thu, 27-Mar-86 07:22:39 EST Organization: U of Wisconsin CS Dept Lines: 33 E.R. Swart has indeed claimed to have shown that P = NP. The result is in University of Guelph research report CIS86-02. The paper is very involved and requires a significant amount of knowledge about mathematical programming. As far as I know the result has not been published. Since the result has not had time to be examined by the computing theory community and since the result contradicts traditional wisdom on the subject some skepticism should be appropriate. Below is a copy of the abstract: A mathematical programming 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 additionl variables, with up to as many as 8 subscripts, this formulation is converted into a linear programming formulation. In the light of results of Kachiyan and Karmarkar concerning the existence of polynomial time algorithms for linear programming this establishes the fact that the Hamilton circuit problem can be solved in polymonial time. Since the Hamilton circuit problem belongs to the set of NP-complete problems it follows immediately that P = NP. His claimed degree of his polynomial time bound for the Hamilton circuit problem is greater than than 25. Once again I would like to state that although no one has found any errors in the work the concensus of the computing community is that there is no way P could equal NP. As a result conventional wisdom would say that there is probally an error is Swart's formulation somewhere. Since the result is so involved and probally at this point only understood by Swart it may be sometime before any finds an error(assuming one exists).