A Polynomial Time Algorithm for the Hamilton Circuit Problem
(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.
Subjects: Computational Complexity (cs.CC)
Cite as: arXiv:1305.5976 [cs.CC]
(or arXiv:1305.5976v1 [cs.CC] for this version)
From: Xinwen Jiang [view email]
[v1] Sun, 26 May 2013 00:40:00 GMT (1363kb)
So, P=NP or not?
We also need a creditable algorithm to tell us if the generated instance contains a simple path. Hence our testing system has three parts: the instance generator, the backtracking algorithm as a benchmark and Z-H algorithm. Until now, since 2010.10.06, more than 52 millions of instances have been generated randomly, each of which has 100 vertices. Some instances contain a simple path while others (it is the majority in all the generated instances) do not. All the results show that our polynomial time algorithm can get the same answer as the backtracking algorithm does. No exception.
Nice try guys, keep it up.