Home > Papers

 
 
A Constructive Algorithm to Prove P=NP
Duan Wenqi * #
College of Economics and Management, Zhejiang Normal University, ZheJiang JinHua 321004
*Correspondence author
#Submitted by
Subject:
Funding: none
Opened online: 7 August 2012
Accepted by: none
Citation: Duan Wenqi.A Constructive Algorithm to Prove P=NP[OL]. [ 7 August 2012] http://en.paper.edu.cn/en_releasepaper/content/4485654
 
 
After reducing the undirected Hamiltonian cycle problem into the TSP problem with cost 0 or 1, we developed an effective algorithm to compute the optimal tour of the transformed TSP. Our algorithm is described as a growth process: initially, constructing 4-vertexes optimal tour; next, one new vertex being added into the optimal tour in such a way to obtain the new optimal tour; then, repeating the previous step until all vertexes are included into the optimal tour. This paper has shown that our constructive algorithm can solve the undirected Hamiltonian cycle problem in polynomial time. According to Cook-Levin theorem, we argue that we have provided a constructive proof of P=NP.
Keywords:Hamiltonian cycle problem; constructive algorithm; P=NP
 
 
 

For this paper
  • ● PDF (0B)
  • ● Revision 0 　　
  • ● Print this paper
  • ● Recommend this paper to a friend
  • ● Add to my favorite list

    Saved Papers

    Please enter a name for this paper to be shown in your personalized Saved Papers list

Tags
Add yours

Related Papers

Statistics
PDF Downloaded 177
Bookmarked 0
Recommend 5
Comments Array
Submit your papers