> There are well-known approximation algorithms for the Traveling Salesman Problem, which is NP-hard Actually, it's either not NP-hard, or not approximable, de

> There are well-known approximation algorithms for the Traveling Salesman Problem, which is NP-hard Actually, it's either not NP-hard, or not approximable, depending on your definition of TSP. Let me clarify. TSP, as most people define it, means "given a graph, find the shortest roundtrip". As you rightly state, this problem can be well approximated. But it's not a decision problem (it doesn't have a yes/no answer), and thus doesn't even fit into categories like "NP" or "NP-complete". Talking about the NP-completess of this "Optimization TSP" is essentially a type error. It's only when we define a "Decision TSP" problem that we can talk about things like NP-hardness. For example, we might ask "Given a graph and a number c, is there a roundtrip of length less than c?". And this new problem is NP-hard. Given any problem in NP, like a SAT instance for example, we can efficiently construct a (usually very contrived) graph that will have a roundtrip of a certain length if and only the original SAT instance is satisfiable. But unlike "Optimization TSP", this "Decision TSP" can't be approximated. It doesn't even make sense to talk about approximations: a roundtrip of length < c can't "almost exist", the answer is always either yes or no. And while an exact solution for Optimization TSP can trivially answer Decision TSP, any approximation of Optimization TSP is essentially useless in solving Decision TSP. That's why TSP (in its optimization form) can be easy to approximate, while also (in its decision form) being NP-hard.