# Is there a lower bound for the computational complexity of the traveling salesman problem?

A (non-mathematician) acquaintance of mine recently proposed to me a polynomial-time algorithm for solving the traveling salesman problem. While I was able to point out a flaw in his approach, it did get me wondering the following question:

Is there a lower bound on the computational complexity for the TSP?

According to wikipedia, it is unknown if there exists a solution that runs in $O(1.9999^n)$. But is it known that any solution must be $O(r^n)$ for some $r>1$? Or is it possible (as surprising as this would be) that there exists a polynomial-time algorithm for this?

(Obviously this would have some major consequences, e.g. P=NP, etc. if such a thing exists. I'm just wondering if we can rule any such solution out out of hand)

• The existence of such a thing is equivalent to P = NP. Hence we can’t. – Emil Jeřábek 3.0 Nov 12 '17 at 14:45
• See the Beardwood–Halton–Hammersley Theorem theoremoftheday.org/OR/BHH/TotDBHH.pdf – Dendi Suhubdy Nov 12 '17 at 15:42
• @DendiSuhubdy What does this fact about random TSP instances have to do with the computational complexity of the problem? – Sasho Nikolov Nov 12 '17 at 23:25
• This question is confusing because you mention P=NP in your last sentence, but the previous one sounds like you do not understand the P vs NP problem and the how the TSP relates to it... – usul Nov 13 '17 at 4:20

The Hamiltonian-circuit problem (which is known to be NP-complete) is polynomially reducible to TSP: Given a graph $G$ on $n$ vertices construct an edge-weighted $K_n$ complete graph with edge weights 0 and 1, so that the weight-0 edges span a subgraph isomorphic to $G$. Now $G$ is Hamiltonian iff the minimal tour in $K_n$ has cost zero. Therefore there can be no poly-time algorithm for TSP unless P=NP.