pruhs@uwvax.UUCP (Kirk Pruhs) (03/25/86)
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).
phr@ucbvax.BERKELEY.EDU (Paul Rubin) (03/26/86)
R. Solovay has apparently found a fatal flaw in Swart's paper (a `proof by example' of a lemma that Solovay doesn't believe to be true). Solovay has written Swart asking if Swart can fix the bug. This info was posted on msgs here by E. L. Lawler.
bill@milford.UUCP (bill) (03/27/86)
> > E.R. Swart has indeed claimed to have shown that P = NP. The result > 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 Hmmm. Isn't he simply 'solving' an ILP problem by relaxing the restriction that the solution be INTEGER vectors? Its well known that LP problems have polynomial solutions. The problem is that the optimal solution with only integer (or 0/1) coordinates is still hard to find even when one finds the optimal over the reals. Of course there might be more hidden in that "additional linear constraints"