The following theorem (from "The Design of approximation algorithms" by Williamson & Shmoys, pg 43) states:

For any $\alpha > 1$, there does not exist an $\alpha$-approximation algorithm for the traveling salesman problem on $n$ cities, provided $P \neq NP$. In fact, the existence of an $O(2^n)$-approximation algorithm for the TSP would similarly imply that $P = NP$.

This theorem is given without a proof. It only explains, before the theorem formally stated, that for any $\alpha > 1$, there does not exist an $\alpha$-approximation algorithm. This part is clear. But the claim that the existence of an $O(2^n)$-approximation algorithm for the TSP would similarly imply that $P = NP$ is not obvious to me. Could someone give me a hint how to prove it or sketch of proof?

  • $\begingroup$ Try using such an algorithm to determine if a given graph is Hamiltonian. $\endgroup$ Nov 10, 2017 at 23:19
  • $\begingroup$ @YuvalFilmus Right. I missed that part of the discussion in the book. It says that we could set the weight of "non-edges" to $\alpha n + 2$ where $\alpha = O(2^n)$. So if the algorithm runs in $O(2^n)$ time, then it is, in fact, still polynomial of the length of input. Thanks! $\endgroup$
    – HardFork
    Nov 11, 2017 at 0:52
  • $\begingroup$ Perhaps you should answer your own question now. $\endgroup$ Nov 11, 2017 at 6:22

1 Answer 1


After @YuvalFilmus' hint it turns out the answer lies in this book. The TSP can be used to solve the Hamiltonian Cycle problem by creating a new graph as following. Given $\alpha > 1$ and a graph $G=\langle V,E \rangle$ we create a new graph $G'=\langle V',E' \rangle$ such that $w(e')= 1$ if $e\in E$, and $w(e')= \alpha n+2$ if $e\notin E$. If $G$ has a Hamiltonian cycle then $G'$ has a tour of length $n$, otherwise each tour has length is at least $(\alpha+1)n + 1$.

Now we run $\alpha$-approximation algorithm for TSP and if the tour computed has cost at most $(\alpha+1)n$ then there is a Hamiltonian cycle in $G$, otherwise there doesn't. If we set $\alpha = O(2^n)$ then we have $O(2^n)$-approximation algorithm. This algorithm runs in $O(f(2^n))$ time for some polynomial $f$, but its time complexity is still polynomial in length of input. This means we would solve the Hamiltonian Cycle problem in polynomial time implying $P=NP$.

  • 1
    $\begingroup$ You have to be a bit careful here, and check that this reduction is polytime. Indeed, you can't choose $\alpha$ arbitrarily large – it needs to be $2^{n^{O(1)}}$. $\endgroup$ Nov 11, 2017 at 8:39
  • $\begingroup$ @YuvalFilmus wouldn't it be $2^{n^{O(f(n))}}$ where $f(n)$ is a polynomial? $\endgroup$
    – HardFork
    Nov 11, 2017 at 8:57
  • 2
    $\begingroup$ It should be $2^{\mathit{poly}(n)}$, since we need the encoding to have polynomial length. $\endgroup$ Nov 11, 2017 at 8:58
  • $\begingroup$ @YuvalFilmus Right, $n^{O(f(n))}$ is exponential. My mistake. $\endgroup$
    – HardFork
    Nov 11, 2017 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.