The PCP theorem establishes that Max-3SAT cannot be approximated to better than 7/8 of optimal unless P=NP. A researcher claims their algorithm guarantees satisfying at least 88% of clauses in polynomial time. If correct, this result would imply:
AA breakthrough in approximation algorithms, but consistent with P≠NP since 88% < 100%
BP=NP, since 88% > 7/8 ≈ 87.5% violates the inapproximability threshold
COnly that the inapproximability bound was slightly off — real bounds have some slack
DNothing surprising — the 7/8 bound applies only to worst-case instances, not to average cases
The PCP-based inapproximability result says no polynomial algorithm can distinguish 'all clauses satisfiable' from 'at most 7/8 + ε clauses satisfiable' unless P=NP. Any algorithm achieving strictly better than 7/8 approximation would break this hardness gap, implying P=NP. The threshold is 7/8 ≈ 87.5%, so 88% > 7/8 would cross it. Interestingly, a simple randomized algorithm (assign each variable uniformly at random) already achieves exactly 7/8 in expectation — so the bound is tight.
Question 2 Multiple Choice
The PCP theorem's most important contribution to the theory of approximation algorithms is:
AProviding faster algorithms for NP-hard problems by reducing the proof size that must be checked
BEstablishing that many NP-hard optimization problems have provable approximation thresholds — ratios below which no polynomial algorithm can go unless P=NP
CShowing that all NP-hard problems have polynomial approximation schemes (PTAS)
DDemonstrating that randomized verification is more powerful than deterministic verification
The PCP theorem's practical impact is inapproximability: it provides the machinery to prove that certain approximation ratios are computationally hard to beat. Before PCP, we had good approximation algorithms but no principled lower bounds — we didn't know whether better ratios were achievable or just undiscovered. PCP-based reductions established matching lower bounds (e.g., set cover's ln n ratio is tight, vertex cover below 1.36 is hard), transforming approximation from a practical art into a precise theory with tight upper and lower bounds.
Question 3 True / False
The PCP theorem implies that for some NP-hard optimization problems, no polynomial-time algorithm can guarantee a solution within any fixed constant factor of optimal, unless P=NP.
TTrue
FFalse
Answer: True
This is a direct consequence of PCP-based inapproximability. For example, the traveling salesman problem without the triangle inequality admits no constant-factor approximation unless P=NP. For vertex cover, no polynomial algorithm can achieve ratio below approximately 1.36. These are not just unknown gaps — they are proven hardness results showing that any algorithm beating the threshold would imply P=NP. The thresholds vary by problem: some have tight constant-factor bounds, others have logarithmic or polynomial hardness gaps.
Question 4 True / False
Since many NP-hard problems have proven inapproximability thresholds, this means approximate solutions to these problems are computationally useless in practice.
TTrue
FFalse
Answer: False
Inapproximability establishes where the theoretical hard wall is — it does not say all approximations fail. Many NP-hard problems have excellent polynomial-time approximation algorithms that come close to (or exactly reach) their inapproximability threshold. Set cover has a greedy (1 + ln n) algorithm that matches its hardness lower bound. TSP with triangle inequality has Christofides' 3/2-approximation. Vertex cover has a simple 2-approximation. Inapproximability tells us where to stop looking for improvement, not that the achievable approximations are useless.
Question 5 Short Answer
Explain the conceptual shift the PCP theorem introduces: what does it mean to say that 'approximation is hardness, measured at a finer scale'?
Think about your answer, then reveal below.
Model answer: Before PCP, hardness was binary: a problem is NP-hard or not. The question was whether an exact solution could be found in polynomial time. PCP reveals that hardness has a continuous structure: for optimization problems, you can ask 'at what approximation ratio does finding a solution become hard?' Some problems have a threshold ratio r* such that polynomial algorithms achieving ratio > r* exist, but achieving ratio > r* + ε for any ε > 0 is NP-hard. Approximation is not an escape from NP-hardness — it is a parameterized version of it, with the approximation ratio as the parameter.
The practical import: we no longer just ask 'is this problem hard?' but 'how hard is it at each approximation level?' This gives a complete picture of what is achievable. For Max-3SAT, we can achieve 7/8 (efficiently) but not 7/8 + ε (unless P=NP). For set cover, we can achieve ln n but not (1 − ε) ln n. The PCP theorem is the tool that pins down these thresholds by converting the question 'can you do better than ratio r?' into a question about NP-membership — the same framework that makes exact NP-hardness proofs work.