approximation algorithm for TSP and P=NP

Question

i recently read an article about approximation algorithms for solving the TSP problem. One of the first theorems in this article states:

if there is an α-approximation algorithm for the TSP (for any α) then P=NP.

directly followed by a theorem which says

Christofides’s algorithm is a 3/2 -approximation algorithm for the metric TSP.

but wouldn't this, referring to the first theorem, imply that P=NP?

Answer 1

I think your sources are misguided.

$MST$ is a trivial 2-approximation for the $TSP$ problem

let $T$ denote the weight of the optimal solution for the $TSP$ problem, and let $M$ denote the weight of the $MST$.

by correctness of $MST$, you immediate get that $M \leq T$

An euler tour on the given $MST$ solves the $TSP$ problem, and its weight is twice that of the $MST$ since it walks every arc exactly twice.

now we get:

$M \leq T \leq 2M$

There is a better approximation, but it involves a complex algorithm with a min-degree spanning tree.

None of the above mean $P=NP$.

Answer 2

"Metric TSP" and "TSP" are not the same. So, both theorems you stated are true, but do not imply P=NP.

In metric TSP, the distances between the cities obey the triangle inequality. This makes the problem much easier to approximate. In plain old TSP they may not. TSP can be used to decide the Hamiltonian cycle problem by putting weight 1 on edges that exist and weight infinity on edges that do not.

The answer from lox only works on metric TSP. But to be fair, usually when people say "TSP" they really mean "metric TSP."