A Proof of Impossibility of a Polynomial-Time Solution of the Traveling Salesman Problem on the Self-Referral Structure of the Global Optimal Tour | Zenodo
Skip to main
You are using an outdated browser. Please upgrade your browser to improve your experience.
Published August 13, 2026
| Version v1
Publication
Open
A Proof of Impossibility of a Polynomial-Time Solution of the Traveling Salesman Problem on the Self-Referral Structure of the Global Optimal Tour
Authors/Creators
Lee, Dorival
Description
This paper presents an information-theoretic proof demonstrating that the general Traveling Salesman Problem (TSP) cannot be solved in polynomial time by any Deterministic Turing Machine ($P \neq NP$). By formalizing an adversarial worst-case model where edge weights are mutually independent and identically distributed random variables, we establish that local evaluations yield zero mutual information regarding global optimality, precluding any macroscopic algebraic shortcuts. Furthermore, we prove that even optimal dynamic programming strategies like the Bellman-Held-Karp algorithm are structurally bounded by an exponential state space $\Omega(2^n)$ because independent sub-tours cannot be losslessly compressed or factored by any deterministic state transition function.
Files
P_Not_Equal_To_NP.pdf
Files<br>(183.8 kB)
Name<br>Size
Download all
P_Not_Equal_To_NP.pdf
md5:e273c59862fb044520f56c3d55cb3782
183.8 kB
Preview
Download
Views
Downloads
Show more details
All versions<br>This version
Views
Total views
Downloads
Total downloads
Data volume
Total data volume
0 Bytes<br>0 Bytes
More info on how stats are collected....
Versions
External resources
Indexed in
OpenAIRE
Communities
Details
DOI
DOI Badge
DOI
10.5281/zenodo.21911759
Markdown
[](https://doi.org/10.5281/zenodo.21911759)
reStructuredText
.. image:: https://zenodo.org/badge/DOI/10.5281/zenodo.21911759.svg<br>:target: https://doi.org/10.5281/zenodo.21911759
HTML
Image URL
https://zenodo.org/badge/DOI/10.5281/zenodo.21911759.svg
Target URL
https://doi.org/10.5281/zenodo.21911759
Resource type<br>Publication
Publisher<br>Zenodo
Rights
License
Creative Commons Attribution 4.0 International
The Creative Commons Attribution license allows re-distribution and re-use of a licensed work on the condition that the creator is appropriately credited.
Read more
Citation
Export
Technical metadata
Created
August 13, 2026
Modified
August 13, 2026
Jump up
This site uses cookies. Find out more on how we use cookies
Accept all cookies<br>Accept only essential cookies