Actually general version of TSP (optimization problem) cannot be approximated to a constant factor in polynomial time unless P = NP. [1] Your confusion likely

Actually general version of TSP (optimization problem) cannot be approximated to a constant factor in polynomial time unless P = NP. [1] Your confusion likely stem from the fact that metric-TSP (a special case of TSP problem where the distance between cities form a metric [2]) is actually APX-complete, which means it can be approximated to a constant factor in polynomial time (Christofides algorithm, approx ratio = 1.5). PS: A potentially interesting aside - Sanjeev Arora, the PhD advisor of Subhash Khot actually got his first Gödel prize (2001) for discovering a PTAS (polynomial time approximation scheme, which in layman term means you can approximate it as close to real answer (but not exactly) as you like in polynomial time) for Euclidean-TSP (independently discovered by Joseph S. B. Mitchell as well). The algorithm make pretty interesting use of Dynamic programming, and was a surprise for the theoretical CS community that time. [1] Brief intuition - HAMILTON-PATH (decision version) can be solved exactly in polynomial time using a constant factor poly time approximation of general TSP (optimization). But since, HAMILTON-PATH is proven to be NP-Complete, then P must equal NP (in which case we can solve all problems in NP and their optimization counterparts exactly in polynomial time anyway). For a formal proof see Khot's lecture notes: http://www.cs.nyu.edu/~khot/lec1.ps http://www.cs.nyu.edu/~khot/lec1.ps (you can find a variety of other similar resources as well, as this is one of the first impossibility proof in almost any graduate level approximation algorithm class). [2] http://en.wikipedia.org/wiki/Metric_(mathematics) http://en.wikipedia.org/wiki/Metric_(mathematics)