Applied Mathematics

Volume 9, Issue 12 (December 2018)

ISSN Print: 2152-7385   ISSN Online: 2152-7393

Google-based Impact Factor: 0.58  Citations  

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

HTML  XML Download Download as PDF (Size: 922KB)  PP. 1351-1359  
DOI: 10.4236/am.2018.912088    1,530 Downloads   6,872 Views  Citations
Author(s)

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

Share and Cite:

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.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.