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

作　　者：Jinliang Wang 

机构地区：[1]Research Institute for ESMD Method and Its Applications, College of Science, Qingdao University of Technology, Qingdao, China

出　　处：《Applied Mathematics》2018年第12期1351-1359,共9页应用数学（英文）

摘　　要：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”.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”.

关 键 词：TRAVELLING SALESMAN PROBLEM P versus NP PROBLEM NP-COMPLETE Computational Complexity Maximum-Deleting Method 

分 类 号：TP30[自动化与计算机技术—计算机系统结构]