Research ArticleOpen AccessGoogle Scholar indexed
Fast Algorithm for the Travelling Salesman Problem and the Proof of P = NP
Research Institute for ESMD Method and Its Applications, College of Science, Qingdao University of Technology, Qingdao, China
- 1 Research Institute for ESMD Method and Its Applications, College of Science, Qingdao University of Technology, Qingdao, China
Applied Mathematics·Volume 09 (2018)·Pages 1351–1359·Published 19 December 2018·DOI10.4236/am.2018.912088
Copy link · social · email
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 ”.
KeywordsTravelling Salesman ProblemP versus NP ProblemNP-CompleteComputational ComplexityMaximum-Deleting Method
- Wikipedia (the Free Encyclopedia), Travelling Salesman Problem. https://en.wikipedia.org/wiki/Travelling_salesman_problem
- Devlin, K.J. (2003) The Millennium Problems: The Seven Greatest Unsolved Mathematical Puzzles of Our Time. Basic Books, New York.
- Cook, S. (2018) Official Problem Description: The P versus NP Problem. http://www.claymath.org/millennium-problems/p-vs-np-problem
- Wikipedia (the Free Encyclopedia), P versus NP Problem. https://en.wikipedia.org/wiki/P_versus_NP_problem
- 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.
- Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco.