[FOM] [1305.5976] A Polynomial Time Algorithm for the Hamilton Circuit Problem

Alasdair Urquhart urquhart at cs.toronto.edu
Fri May 31 23:14:33 EDT 2013


These "proofs" are a dime a dozen.
If FOM subscribers are interested in them,
they will find a very lengthy catalogue in the
"P-versus-NP page" maintained by GJ Woeginger

http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

Xinwen Jiang's "proof" is discussed in item 53
of the P-versus-NP page.


On Wed, 29 May 2013, // ravi wrote:

>
>
> I haven’t seen this appear on the list, so:
>
> http://arxiv.org/abs/1305.5976
>
>> A Polynomial Time Algorithm for the Hamilton Circuit Problem
>>
>> Xinwen Jiang
>> (Submitted on 26 May 2013)
>> In this paper, we introduce a so-called Multistage graph Simple Path (MSP) problem and show that the Hamilton Circuit (HC) problem can be polynomially reducible to the MSP problem. To solve the MSP problem, we propose a polynomial algorithm and prove its NP-completeness. Our result implies NP=P.
>
>
> 	—ravi


More information about the FOM mailing list