Fast Algorithm for the Travelling Salesman Problem and the Proof of P = NP

Show more

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**”.

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.