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 supports Monica 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

2 Answers

There is a (nearly) trivial linear-time lower bound, because it takes linear time to read in the input. (I say this is nearly trivial because you do have to argue that it is necessary to examine at least a constant fraction of the input to get the right answer.)

Some slightly super-linear time bounds are known, under certain assumptions about the computational model. This was discussed in another MO question. Note that once you start talking about linear-time algorithms then you unavoidably get into picky details about how the input is represented and exactly what the computational model is, because changing the format of the input might itself take super-linear time, and how fast your computer can access a particular bit can make a significant difference.

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.

• But 1.99999^n is not polynomial. – gnasher729 Nov 12 '17 at 16:24
• @gnasher729 Polynomial is certainly a lower bound, though. – LegionMammal978 Nov 12 '17 at 22:35