The Knapsack problem is NP-hard, but it has a fully polynomial-time approximation scheme (FPTAS). Maximum Clique is also NP-hard. What does hardness of approximation theory tell us about Maximum Clique?
AMaximum Clique must also have an FPTAS since both problems are NP-hard
BMaximum Clique cannot be approximated within a factor of n^(1-ε) for any ε > 0, unless P = NP — making it essentially inapproximable
CMaximum Clique has a constant-factor approximation, similar to Vertex Cover's 2-approximation
DMaximum Clique is easier to approximate than Knapsack because cliques are simpler structures
This is the central lesson of hardness of approximation: NP-hardness of the decision problem tells you almost nothing about approximability of the optimization version. Knapsack has an FPTAS — you can get within (1+ε) of optimal for any ε. Maximum Clique is at the opposite extreme: no polynomial-time algorithm can find a clique within a factor n^(1-ε) of the largest, for any ε > 0, unless P = NP. Two problems can be equally hard to solve exactly but live in completely different approximability classes. This is why the classification into tiers (FPTAS, constant-factor, logarithmic, inapproximable) is so important.
Question 2 Multiple Choice
The PCP theorem enables inapproximability proofs by showing that certain gap problems are NP-hard. What is a 'gap problem' in this context?
AA problem where the optimal solution has a gap between its upper and lower bounds
BDistinguishing between instances where the optimum is above one threshold versus below another threshold
CA problem that is easy in the average case but hard in the worst case
DA problem where approximation algorithms leave a gap between the achieved ratio and the optimal ratio
A gap problem asks: given an instance, is the optimum ≥ α (the 'yes' case) or ≤ β (the 'no' case), where α > β? If this distinction is NP-hard, then no polynomial-time algorithm can achieve an approximation ratio better than α/β (otherwise it could solve the gap problem). The PCP theorem transforms NP membership proofs into a form where a random subset of bits can certify correctness, enabling reductions that create these gaps. The magic is that these gap reductions come from the structure of probabilistically checkable proofs, not from ad hoc constructions.
Question 3 True / False
Most NP-hard optimization problems are equally difficult to approximate — if one has no constant-factor approximation, very few of them do.
TTrue
FFalse
Answer: False
This is the key misconception that hardness of approximation corrects. NP-hard problems span a wide spectrum of approximability. Some have FPTAS (Knapsack), some have constant-factor approximations (Vertex Cover: 2, TSP with triangle inequality: 1.5), some have only logarithmic approximations (Set Cover: O(log n)), and some are essentially inapproximable (Maximum Clique). The NP-hardness of the decision problem and the approximability of the optimization problem are largely orthogonal questions — the latter requires its own theory.
Question 4 True / False
If a polynomial-time algorithm cannot solve an NP-hard decision problem exactly, it can seldom achieve any useful approximation guarantee for the corresponding optimization problem either.
TTrue
FFalse
Answer: False
Many NP-hard optimization problems admit excellent polynomial-time approximations despite having intractable exact decision versions. The Knapsack problem has an FPTAS producing solutions within (1+ε) of optimal for any ε. Christofides' algorithm gives a 1.5-approximation for metric TSP. These algorithms are polynomial-time and achieve strong guarantees — they just don't find the exact optimum. The inability to solve the decision version exactly says nothing about how close a polynomial algorithm can get to the optimum value.
Question 5 Short Answer
Why is the classification of NP-hard problems into approximability tiers (FPTAS, constant-factor, logarithmic, inapproximable) more practically useful than simply knowing a problem is NP-hard?
Think about your answer, then reveal below.
Model answer: NP-hardness only tells you that exact polynomial-time solution is unlikely. Approximability tiers tell you what quality of solution is achievable efficiently, which directly determines algorithm design strategy. If a problem has an FPTAS, you can get arbitrarily close to optimal — near-exact solutions are practical. A constant-factor approximation means you can guarantee quality within a fixed multiple of optimal. An inapproximability result tells you no polynomial algorithm will ever give a meaningful guarantee — you should use heuristics, restrict to special cases, or reformulate the problem. This prevents wasted effort chasing approximation guarantees that provably cannot exist.
The tiers matter because they set realistic expectations. A practitioner facing an NP-hard problem must decide: should I invest in approximation algorithm research, or switch to heuristics? If the problem is in the 'inapproximable' tier (like Max Clique), investing in approximation theory is futile — provably no good approximation can exist. If it has a PTAS, investing in tightening the approximation ratio is worthwhile. The classification guides resource allocation and sets the ceiling for what algorithms can achieve.