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)
 A: 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.
A: 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.
