3
$\begingroup$

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)

Improve this question
$\endgroup$
4
  • 9
    $\begingroup$ The existence of such a thing is equivalent to P = NP. Hence we can’t. $\endgroup$
    – Emil Jeřábek
    Commented Nov 12, 2017 at 14:45
  • 1
    $\begingroup$ See the Beardwood–Halton–Hammersley Theorem theoremoftheday.org/OR/BHH/TotDBHH.pdf $\endgroup$
    – Dendi Suhubdy
    Commented Nov 12, 2017 at 15:42
  • 2
    $\begingroup$ @DendiSuhubdy What does this fact about random TSP instances have to do with the computational complexity of the problem? $\endgroup$
    – Sasho Nikolov
    Commented Nov 12, 2017 at 23:25
  • 3
    $\begingroup$ 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... $\endgroup$
    – usul
    Commented Nov 13, 2017 at 4:20

2 Answers 2

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
8
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ But 1.99999^n is not polynomial. $\endgroup$
    – gnasher729
    Commented Nov 12, 2017 at 16:24
  • 1
    $\begingroup$ @gnasher729 Polynomial is certainly a lower bound, though. $\endgroup$
    – LegionMammal978
    Commented Nov 12, 2017 at 22:35

You must log in to answer this question.