TITLE:
Fast Algorithm for the Travelling Salesman Problem and the Proof of P = NP
AUTHORS:
Jinliang Wang
KEYWORDS:
Travelling Salesman Problem, P versus NP Problem, NP-Complete, Computational Complexity, Maximum-Deleting Method
JOURNAL NAME:
Applied Mathematics,
Vol.9 No.12,
December
20,
2018
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”.