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)

equivalentto P = NP. Hence we can’t. $\endgroup$ – Emil Jeřábek supports Monica Nov 12 '17 at 14:45