A research paper proves that achieving a 1.5-approximation for Problem X is NP-hard. What does this mean in practice?
ANo algorithm can solve Problem X at all, even approximately
BAny polynomial-time algorithm for Problem X must return solutions within a factor of 1.5 of optimal
CNo polynomial-time algorithm can guarantee a solution within a factor of 1.5 of optimal — unless P = NP
DProblem X is harder than NP-hard, placing it in a strictly higher complexity class
An inapproximability result of ratio ρ means that a ρ-approximation algorithm would imply P = NP — so no such algorithm exists under the standard assumption. It does NOT mean no algorithm can solve the problem at all (exact exponential-time solutions exist), and it doesn't say anything about what approximations can be achieved in superpolynomial time. Problem X remains NP-hard; inapproximability is a statement about what polynomial-time algorithms can guarantee, not a reclassification into a higher class.
Question 2 Multiple Choice
What distinguishes a gap-preserving reduction (used in inapproximability proofs) from an ordinary polynomial-time NP-hardness reduction?
AGap-preserving reductions must run in linear time; ordinary reductions only need polynomial time
BGap-preserving reductions preserve a gap in objective value between YES and NO instances, showing that even approximate discrimination is hard; ordinary reductions only need to preserve feasibility
CGap-preserving reductions work on maximization problems; ordinary reductions work on decision problems
DGap-preserving reductions require the PCP theorem as a subroutine in the reduction itself
An ordinary NP-hardness reduction from 3-SAT to Problem X maps satisfiable instances to YES instances and unsatisfiable ones to NO instances, showing exact solution is hard. A gap-preserving reduction additionally ensures that YES instances have objective value ≥ α (high) and NO instances have objective value ≤ β (low), with α/β > ρ. This gap means that any ρ-approximation algorithm would solve the 3-SAT instance — so approximation within ratio ρ is also NP-hard. The reduction must carefully track how transformation affects objective values, not just feasibility.
Question 3 True / False
The PCP theorem implies that for some constant ε > 0, no polynomial-time algorithm can achieve a (1 − ε)-approximation for MAX-3SAT unless P = NP.
TTrue
FFalse
Answer: True
This is one of the foundational consequences of the PCP theorem. The theorem provides a characterization of NP where proofs can be checked by reading only a constant number of bits — this yields a gap in the MAX-3SAT instance (satisfiable vs. at most (1−ε)-satisfiable) that is NP-hard to close. Any polynomial-time approximation beyond this constant ratio would allow efficient discrimination of satisfiable from nearly-unsatisfiable instances, collapsing NP into P. This base inapproximability for MAX-3SAT propagates via gap-preserving reductions to other problems.
Question 4 True / False
Since most NP-hard problem is hard to solve exactly, no NP-hard optimization problem can be efficiently approximated to within any fixed constant ratio.
TTrue
FFalse
Answer: False
This is the core misconception that hardness of approximation addresses. Many NP-hard optimization problems admit excellent approximation algorithms: Vertex Cover has a 2-approximation, various scheduling problems admit polynomial-time approximation schemes (PTAS) achieving (1+ε)-approximation for any ε > 0. NP-hardness of exact solution says nothing directly about approximability. Hardness of approximation is a *separate, additional* result showing that for specific problems, even approximation to within certain ratios is NP-hard. Some NP-hard problems are easy to approximate; others (like MAX-CLIQUE) are essentially impossible.
Question 5 Short Answer
Why does proving that a problem is NP-hard not automatically tell you how hard it is to approximate, and what additional machinery is needed?
Think about your answer, then reveal below.
Model answer: An NP-hardness proof shows that no polynomial-time algorithm can find the exact optimal solution unless P = NP — but it says nothing about finding a near-optimal solution. To show approximation hardness, you need a gap-preserving reduction that maps YES instances to instances with high objective value and NO instances to instances with low objective value, such that any approximation algorithm achieving ratio ρ would distinguish them and solve the NP-hard source problem. The PCP theorem is the key tool that creates this gap 'for free' for MAX-3SAT — it reformulates satisfiability so that valid proofs are accepted and invalid ones are rejected with constant probability using only constant-many bit checks, which directly translates into a multiplicative gap in the MAX-3SAT objective.
The conceptual shift is from 'can you find an exact solution?' to 'can you distinguish between a solution near the optimum and one far from it?' A problem can be NP-hard to solve exactly but still easy to approximate (e.g., some scheduling problems). The PCP theorem is surprising precisely because it shows this isn't always the case — for some problems, even approximation within a constant factor is as hard as exact solution.