Back
 AM  Vol.9 No.12 , December 2018
Fast Algorithm for the Travelling Salesman Problem and the Proof of P = NP
Abstract:
In the theory of computational complexity, the travelling salesman problem is a typical one in the NP class. With the aid of a brand-new approach named “maximum-deleting method”, a fast algorithm is constructed for it with a polynomial time of biquadrate, which greatly reduces the computational complexity. Since this problem is also NP-complete, as a corollary, P = NP is proved to be true. It indicates the crack of the well-known open problem named “P versus NP”.
Cite this paper: Wang, J. L. (2018) Fast Algorithm for the Travelling Salesman Problem and the Proof of P = NP. Applied Mathematics, 9, 1351-1359. doi: 10.4236/am.2018.912088.
References

[1]   Wikipedia (the Free Encyclopedia), Travelling Salesman Problem.
https://en.wikipedia.org/wiki/Travelling_salesman_problem

[2]   Devlin, K.J. (2003) The Millennium Problems: The Seven Greatest Unsolved Mathematical Puzzles of Our Time. Basic Books, New York.

[3]   Cook, S. (2018) Official Problem Description: The P versus NP Problem.
http://www.claymath.org/millennium-problems/p-vs-np-problem

[4]   Wikipedia (the Free Encyclopedia), P versus NP Problem.
https://en.wikipedia.org/wiki/P_versus_NP_problem

[5]   Cook, S. (1971) The Complexity of Theorem-Proving Procedures. Conference Record of Third Annual ACM Symposium on Theory of Computing, ACM, New York, 151-158.

[6]   Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco.

 
 
Top