A logistics company needs an optimal delivery route for 50 cities. They say: 'TSP is NP-hard, so finding a good route is hopeless — we'll just use any path.' What is wrong with this reasoning?
ANothing — NP-hardness means no good solution can be found efficiently, so any route is as good as any other
BNP-hardness rules out exact optimal solutions in polynomial time, but does not rule out approximations — for metric TSP, the Christofides algorithm guarantees a tour within 1.5× optimal in polynomial time
CTSP is actually polynomial for 50 cities, so brute force would work fine
DTSP is NP-hard only for non-Euclidean distances; for real-world road networks it is polynomial
NP-hardness means no known polynomial-time algorithm finds the exact optimum, but it says nothing about how far a polynomial-time algorithm can deviate from optimal. The Christofides algorithm runs in polynomial time and guarantees a tour of length at most 3/2 times the optimal — for many practical purposes, a near-optimal route is good enough. 'NP-hard therefore hopeless' conflates exact optimization with approximation. TSP is a paradigmatic case where approximation algorithms rescue practical utility from theoretical intractability.
Question 2 Multiple Choice
The decision version of TSP (is there a tour of length ≤ k?) is NP-complete. The optimization version (find the shortest tour) is NP-hard. What is the key distinction between these two characterizations?
ANP-complete problems are strictly harder than NP-hard problems
BNP-completeness applies to decision problems that are both in NP (verifiable in poly-time) and NP-hard; the optimization version is NP-hard but is not itself a decision problem in NP, since 'optimal' cannot be verified without solving the problem
CThe optimization version is also in NP because you can verify a given tour's length in polynomial time
DNP-hard means the problem cannot be solved; NP-complete means it can be solved with exponential resources
NP-completeness is defined for decision problems: a problem is NP-complete if it is in NP (a 'yes' certificate can be verified in poly-time) and is NP-hard (every NP problem reduces to it). For the decision TSP, a certificate is simply the tour itself — sum the edge weights, check ≤ k: poly-time. The optimization version asks for the minimum — you can verify a candidate tour's length, but you cannot verify that it is optimal without ruling out all shorter tours (which requires solving the problem). So the optimization version is NP-hard but not in NP, hence not NP-complete. This distinction is not pedantry — it matters for the theory of what kinds of reductions and approximation results apply.
Question 3 True / False
The Christofides algorithm solves TSP optimally in polynomial time for metric instances.
TTrue
FFalse
Answer: False
This is the most important misconception to correct. The Christofides algorithm is an approximation algorithm: it runs in polynomial time and guarantees a tour of length at most 3/2 times the optimal, but it does not find the optimal tour. Finding the optimal TSP tour remains NP-hard even for metric instances — no polynomial-time exact algorithm is known. Christofides is celebrated precisely because achieving a guaranteed constant factor (1.5) in polynomial time is a non-trivial result, distinct from exactness.
Question 4 True / False
For general TSP without the triangle inequality, no polynomial-time algorithm can achieve any constant-factor approximation guarantee unless P = NP.
TTrue
FFalse
Answer: True
This is a sharp contrast with metric TSP. Without the triangle inequality, any constant-factor approximation can be shown to imply a polynomial-time solution for Hamiltonian cycle (via a reduction that assigns very large weights to missing edges). Since Hamiltonian cycle is NP-complete, a constant-factor approximation for general TSP would imply P = NP. The metric constraint (triangle inequality) is not just a simplification — it is the structural property that makes constant-factor approximation possible at all. Removing it makes TSP inapproximable.
Question 5 Short Answer
Explain why TSP is NP-hard to solve exactly, yet a polynomial-time 3/2-approximation exists for metric TSP. What property of metric TSP enables the approximation?
Think about your answer, then reveal below.
Model answer: TSP is NP-hard because the search space of all possible tours grows factorially with n, and no efficient way to navigate it toward the optimum is known. However, for metric TSP (where edge weights satisfy the triangle inequality), the Christofides algorithm exploits structure: it finds a minimum spanning tree (polynomial), adds a minimum weight perfect matching on odd-degree vertices (polynomial), and constructs an Euler tour that shortcuts repeated vertices. The triangle inequality guarantees that shortcuts never increase total distance — so detours are safe to eliminate. This structural property allows the algorithm to bound the tour length at 3/2 × optimal. For general TSP without the triangle inequality, shortcuts can be arbitrarily costly, so this argument breaks down and no constant-factor approximation is achievable unless P = NP.
The key insight is that NP-hardness and approximability are separate properties. A problem can be NP-hard to solve exactly but still admit efficient approximation. Metric TSP is NP-hard but 3/2-approximable. Other problems (like general TSP) are NP-hard and also inapproximable. The triangle inequality is the structural bridge that separates these two cases for TSP specifically.