How to prove non-existence of $O(2^n)$ approximation algorithm solving TSP?
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 &gt; 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$.