47.03.06 · theoretical-cs / 03-advanced-complexity

Hardness of Approximation: Inapproximability of MAX-3SAT and Vertex Cover

shipped3 tiersLean: nonepending prereqs

Anchor (Master): Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 11; Arora, Lund, Motwani, Sudan and Szegedy 1998 Proof Verification and the Hardness of Approximation Problems (JACM) (PCP theorem proof, optimal inapproximability via Håstad's 3-bit PCP)

Intuition Beginner

Some problems are hard to solve exactly. We know this from NP-completeness: finding the smallest vertex cover in a graph, or the maximum number of satisfiable clauses in a 3SAT formula, is believed to require exponential time. But what if we only need an approximate answer? Could we find a vertex cover that is at most twice the optimal size? Or satisfy at least 90% of clauses?

The answer depends on the problem, and it is sometimes a definitive no. The theory of hardness of approximation tells us not just that finding the exact optimum is hard, but that even getting close to it is hard. For some problems, there is a hard wall: no efficient algorithm can guarantee a solution within a certain ratio of the optimum, unless P equals NP.

The key tool is the PCP theorem. It says that proofs of NP statements can be checked by reading only a constant number of bits of the proof. This sounds like a statement about verification, but it has a striking consequence for optimisation: it creates a gap in the objective function. The gap makes it NP-hard to tell whether the optimum is large or small, which means no approximation algorithm can cross the gap.

Visual Beginner

Consider MAX-3SAT on a formula with 8 clauses. Each clause has exactly 3 literals.

Satisfiable formula:     All 8/8 clauses satisfied (optimal)
Random assignment:       ~7/8 of clauses satisfied on expectation
Hard gap instance:       Either 8/8 OR at most 7/8 + eps satisfied
                          (telling which is NP-hard)

Scenario	Fraction satisfiable	Approximable?
Satisfiable instance	1.0	Find any satisfying assignment (NP-hard)
General instance	Between 7/8 and 1.0	Ratio 8/7 is best possible (P)
Gap instance (PCP)	Either 1.0 or at most 7/8 + eps	Telling apart is NP-hard

The gap is the difference between the two thresholds in the gap instance. The PCP theorem converts any NP-hard decision problem into a gap-3SAT instance, making the gap version itself NP-hard.

Worked example Beginner

We have a 3CNF formula with 6 clauses:

$(x_{1} \lor x_{2} \lor x_{3}) \land (\overset{x}{ˉ}_{1} \lor x_{2} \lor \overset{x}{ˉ}_{3}) \land (x_{1} \lor \overset{x}{ˉ}_{2} \lor x_{3}) \land (\overset{x}{ˉ}_{1} \lor \overset{x}{ˉ}_{2} \lor \overset{x}{ˉ}_{3}) \land (x_{1} \lor x_{2} \lor \overset{x}{ˉ}_{3}) \land (\overset{x}{ˉ}_{1} \lor x_{2} \lor x_{3})$

A random truth assignment satisfies each clause with probability 7/8 (the only way a clause fails is if all three literals are false). So a random assignment satisfies $6 \times 7/8 = 5.25$ clauses on expectation.

Can we do better? For this small instance, we can try all 8 truth assignments and find the best one. The assignment $x_{1} = T, x_{2} = T, x_{3} = F$ satisfies all 6 clauses.

But for large formulas with thousands of variables, exhaustive search is impossible. And the PCP theorem says something stronger: there exist formulas where no efficient algorithm can reliably tell whether all clauses are satisfiable or only 7/8 + eps can be satisfied. The gap between 1.0 and 7/8 + eps is the inapproximability gap.

Check your understanding Beginner

Formal definition Intermediate+

Definition (PCP verifier). A $(r, q)$ -PCP verifier for a language $L$ is a probabilistic polynomial-time Turing machine $V$ that, given input $x$ and oracle access to a proof string $π$ , uses at most $r (∣ x ∣)$ random bits and queries at most $q (∣ x ∣)$ bits of $π$ , such that:

(Completeness) If $x \in L$ , there exists $π$ such that $Pr [V^{π} (x) accepts] = 1$ .
(Soundness) If $x \in / L$ , then for every $π$ , $Pr [V^{π} (x) accepts] \leq 1/2$ .

Theorem (PCP theorem, Dinur 2007 / Arora-Safra 1998). $N P = P C P (lo g n, 1)$ .

Definition (gap problem). For a maximisation problem with optimum $O P T$ , the $(c, s)$ -gap problem asks: given an instance, output YES if $O P T \geq c$ and NO if $O P T \leq s$ , with the promise that one of these holds.

Definition (approximation ratio). An algorithm $A$ is an $α$ -approximation for a maximisation problem if for every instance, $A$ produces a solution with value at least $α \cdot O P T$ . For minimisation, $A$ produces a solution with value at most $α \cdot O P T$ .

Counterexamples to common slips

"The PCP theorem says NP proofs can be checked quickly." The verification was already polynomial; the novelty is that only O(1) bits of the proof are read, yet soundness is maintained with constant probability.
"Inapproximability means no algorithm works at all." It means no algorithm achieves a ratio better than a specific threshold. MAX-3SAT has a 7/8-approximation (random assignment), but no $(7/8 + ε)$ -approximation unless P = NP.
"Hardness of approximation is separate from the PCP theorem." The PCP theorem is the engine of all modern inapproximability results. Every hardness-of-approximation result for an NP-hard optimisation problem ultimately reduces to it.

Key theorem with proof Intermediate+

Theorem (Håstad's optimal inapproximability for MAX-3SAT). For every $ε > 0$ , it is NP-hard to distinguish satisfiable 3CNF formulas from 3CNF formulas where at most a $7/8 + ε$ fraction of clauses are simultaneously satisfiable. Consequently, MAX-3SAT is NP-hard to approximate within factor $7/8 + ε$ for any $ε > 0$ .

Proof sketch. Start from the PCP theorem NP = PCP(log n, 1). The verifier $V$ for SAT uses $O (lo g n)$ random bits $r$ and reads $q = O (1)$ bits of the proof $π$ . Håstad's 3-bit PCP ensures $q = 3$ : the verifier reads exactly 3 bits of $π$ and accepts iff the XOR of those 3 bits equals 0 (or 1, depending on the test).

Construct a 3CNF formula from this verifier. For each random string $r$ , the verifier's test on bits $i_{r}, j_{r}, k_{r}$ of $π$ becomes a clause on variables $y_{i_{r}}, y_{j_{r}}, y_{k_{r}}$ (the proof bits). The clause is satisfied iff the test passes. This gives a 3CNF formula $φ$ with one clause per random string.

Completeness. If the original formula is satisfiable, there exists a proof $π$ that makes $V$ accept with probability 1. The assignment $y_{i} = π_{i}$ satisfies all clauses of $φ$ .

Soundness. If the original formula is unsatisfiable, every proof $π$ makes $V$ accept with probability at most $α$ for some constant $α < 1$ . Håstad's analysis improves this to $α = 1/2 + δ$ for some $δ > 0$ , and Fourier analysis of the long code shows the rejection probability can be boosted to make $α \leq 7/8 + ε$ .

The random assignment satisfies $7/8$ of clauses on expectation (each 3-variable clause is satisfied by 7 of 8 assignments). So $O P T \geq 7/8 \cdot m$ where $m$ is the number of clauses. If we could approximate within $7/8 + ε$ , we could distinguish $O P T = m$ from $O P T \leq (7/8 + ε) m$ , which is NP-hard by the gap above. $□$

Bridge. The PCP theorem is the foundational reason that approximation resistance exists: by encoding NP-hardness into a constant-query verifier, it creates an objective-function gap that no polynomial-time algorithm can cross. This builds toward the approximation algorithms of 47.04.08 where we see that some problems (like Vertex Cover with ratio 2) are far from their inapproximability bound, while MAX-3SAT sits exactly at the limit. The central insight is that the PCP theorem converts a decision problem (is the formula satisfiable?) into a structural property of the solution landscape (either a perfect solution exists or every solution is far from perfect), and this is exactly the pattern that appears again in 47.03.04 where interactive proofs achieve their power through a similar gap between completeness and soundness. The bridge is that hardness of approximation is not a separate phenomenon from computational hardness but a restatement of it at the level of solution quality.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove that if MAX-E3SAT (exact 3SAT, where each clause has exactly 3 distinct variables) can be approximated within factor $7/8 + ε$ for some $ε > 0$ , then P = NP.

Hint

Use Håstad's result and the fact that SAT is NP-complete.

Answer

By Håstad's theorem, it is NP-hard to distinguish satisfiable E3CNF formulas from those where at most a $7/8 + ε$ fraction of clauses are satisfiable. If an algorithm $A$ achieves ratio $7/8 + ε$ , then on a satisfiable formula, $A$ returns an assignment satisfying at least $(7/8 + ε) \cdot O P T = (7/8 + ε) \cdot m$ clauses. But if the formula is satisfiable, $O P T = m$ , so $A$ satisfies at least $(7/8 + ε) \cdot m$ clauses. If the formula is not satisfiable, then at most $(7/8 + ε) \cdot m$ clauses can be satisfied. Wait—this gives a contradiction only at the boundary. More precisely: given any SAT instance $φ$ , reduce it to a gap-E3SAT instance via the PCP theorem. If $φ$ is satisfiable, the gap instance has $O P T = m$ . If not, $O P T \leq (7/8 + ε /2) m$ . An algorithm with ratio $7/8 + ε$ would return at least $(7/8 + ε) \cdot O P T$ clauses. In the YES case, that is at least $(7/8 + ε) m$ . In the NO case, at most $(7/8 + ε /2) m < (7/8 + ε) m$ . So the algorithm distinguishes the two cases, solving SAT in polynomial time. This implies P = NP.

Exercise 4 (medium, symbolic).

A gap-producing reduction from 3SAT to Vertex Cover produces a graph $G$ from a 3CNF formula $φ$ such that: if $φ$ is satisfiable, then $G$ has a vertex cover of size at most $k$ ; if $φ$ is unsatisfiable, then every vertex cover of $G$ has size at least $α \cdot k$ for some constant $α > 1$ . Show that this implies Vertex Cover is NP-hard to approximate within factor $α$ .

Answer

Suppose there exists a polynomial-time $α^{'}$ -approximation algorithm $A$ for Vertex Cover with $α^{'} < α$ . Given a 3CNF formula $φ$ , apply the gap-producing reduction to obtain $G$ and $k$ . Run $A$ on $G$ to get a vertex cover $C$ with $∣ C ∣ \leq α^{'} \cdot O P T (G)$ . If $φ$ is satisfiable, $O P T (G) \leq k$ , so $∣ C ∣ \leq α^{'} \cdot k < α \cdot k$ . If $φ$ is unsatisfiable, $O P T (G) \geq α \cdot k$ , so $∣ C ∣ \geq O P T (G) \geq α \cdot k > α^{'} \cdot k$ . Therefore, $∣ C ∣ < α \cdot k$ iff $φ$ is satisfiable, solving SAT in polynomial time. So Vertex Cover cannot be approximated within $α$ unless P = NP.

Exercise 6 (hard, symbolic).

Let MAX-E3SAT-Ek denote the constraint satisfaction problem where each clause involves exactly 3 variables from a Boolean domain and each variable appears in exactly $k$ clauses. Prove that for sufficiently large $k$ , MAX-E3SAT-Ek is NP-hard to approximate within $7/8 + ε$ for any $ε > 0$ .

Hint

Use the fact that the PCP theorem can be instantiated on regular constraint graphs (each variable has bounded degree) and apply expander graph techniques to regularise the instance.

Answer

Starting from a general MAX-E3SAT instance $φ$ , construct an expander graph $H$ on the variable set. Replace each occurrence of variable $x_{i}$ in clause $C_{j}$ with a new variable $x_{i, j}$ , adding consistency constraints $x_{i, j} = x_{i, j^{'}}$ using 3-clauses over the edges of $H$ . Since $H$ is an expander, the soundness analysis transfers: if the original instance has OPT less than $7/8 + ε$ , then after the consistency constraints, any assignment violates at least a constant fraction of either the original clauses or the consistency constraints. The number of constraints per variable becomes $O (k)$ for some $k = O (1)$ . The resulting instance is an E3SAT-Ek instance (after adjusting for parity), and the gap $(1, 7/8 + ε)$ is preserved up to constant factors. For sufficiently large $k$ , the soundness error can be absorbed, and Håstad's hardness carries through.

Exercise 7 (hard, symbolic).

The Unique Games Conjecture (UGC) of Khot (2002) states that for every $ε, δ > 0$ , there exists an alphabet size $k$ such that it is NP-hard to distinguish whether a Unique Label Cover instance has value at least $1 - ε$ or at most $δ$ . Assuming the UGC, prove that Vertex Cover is hard to approximate within $2 - ε$ for any $ε > 0$ .

Hint

Use the reduction of Khot and Regev (2008) from Unique Label Cover to Vertex Cover.

Answer

Given a Unique Label Cover instance $Λ$ on graph $G = (V, E)$ with alphabet $Σ$ , construct a new graph $G^{'}$ as follows. The vertex set of $G^{'}$ consists of pairs $(v, a)$ for $v \in V$ and $a \in Σ$ . For each edge $(u, v) \in E$ with permutation $π_{uv}$ , add an edge between $(u, a)$ and $(v, π_{uv} (a))$ for each $a \in Σ$ . A vertex cover in $G^{'}$ selects vertices $(v, a)$ ; the complement is an independent set. If $Λ$ has value $1 - ε$ , then the labelling $ℓ$ gives an independent set ${(v, ℓ (v)) : v \in V}$ of size $∣ V ∣$ in $G^{'}$ , so the vertex cover has size $∣ V ∣ (∣Σ∣ - 1)$ . If $Λ$ has value at most $δ$ , Khot and Regev show that every independent set has size at most $(δ + o (1)) ∣ V ∣$ , giving a vertex cover of size at least $∣ V ∣∣Σ∣ (1 - δ - o (1))$ . The ratio is $\frac{∣Σ∣ ( 1 - δ )}{∣Σ∣ - 1} \to 2$ as $∣Σ∣ \to \infty$ and $δ \to 0$ , proving hardness within $2 - ε$ . Rubric: full credit for constructing the label-cover to vertex-cover graph and bounding the independent set sizes in both cases.

Exercise 8 (hard, symbolic).

Prove that Set Cover is NP-hard to approximate within factor $(1 - ε) ln n$ for every $ε > 0$ , where $n$ is the number of elements. (This result is due to Dinur and Steurer, 2014.)

Hint

Reduce from the gap version of 3SAT via the PCP theorem. Use the FGLSS reduction to create a Set Cover instance where each set corresponds to a satisfying assignment for a clause, and each element corresponds to a pair of contradictory proof fragments.

Answer

The reduction of Dinur and Steurer starts from a $(1, 7/8 + ε)$ -gap 3SAT instance with $m$ clauses and $n$ variables. Construct a Set Cover instance: the universe $U$ consists of all $2^{m}$ clause-satisfaction patterns (or a polynomial-sized representative subset via the PCP structure). For each truth assignment $a \in {0, 1}^{n}$ , create a set $S_{a}$ containing the satisfaction pattern of $a$ . The key insight is that if the formula is satisfiable, one set covers the "yes" element, and a small collection of sets (one per random string in the PCP) covers everything. If the formula is far from satisfiable, then by the PCP soundness, any cover must include many sets. The analysis uses the fact that the PCP verifier's constraint graph has a certain structure (bounded degree, good expansion) and shows that the cover size is at least $Ω (m / lo g m)$ in the NO case, compared to $O (m / lo g m / ln m)$ in the YES case. This gives a factor $Ω (lo g n)$ hardness, matching the greedy algorithm's $O (lo g n)$ upper bound. The precise statement is hardness within $(1 - ε) ln n$ . Rubric: full credit for describing the reduction from gap-3SAT and connecting PCP soundness to the cover size gap.

Lean formalization Intermediate+

Mathlib has no formalization of the PCP theorem, gap-producing reductions, or any hardness-of-approximation result. A formalization would need a PCP.Verifier structure with randomness, query_count, completeness, and soundness fields; a proof of the PCP theorem itself (NP = PCP(log n, 1)); and gap-preserving reduction constructions for specific problems like MAX-3SAT, Vertex Cover, and Set Cover. The gap between Mathlib's current state and a formal PCP theorem is substantial—it would require building the entire algebraic PCP machinery (low-degree tests, sum-check protocol, composition). This unit ships without a lean_module.

Advanced results Master

Three families of results sharpen the boundary between what is approximable and what is not.

Result 1 (optimal inapproximability via the long code). The Håstad 3-bit PCP achieves optimal hardness for several CSPs simultaneously. The technique encodes proof bits using the long code of a function $f : {0, 1}^{k} \to {0, 1}$ , defined by $Long (f) = (⨁_{i : S_{i} = 1} f (i))_{S \subseteq [k]}$ . The Fourier analysis of this encoding shows that any accepted proof must correlate with a dictator function, and the acceptance probability is bounded by the maximum Fourier coefficient of the proof function plus $1/2 + ε$ . This gives hardness $7/8 + ε$ for MAX-3SAT, $1/2 + ε$ for MAX-LIN-2, and $n^{1 - ε}$ for Max-Clique ^{[Håstad 2001]}.

Result 2 (the UGC and its consequences). Khot's Unique Games Conjecture (2002) posits that Unique Label Cover is NP-hard to approximate within any constant. If true, it implies a dramatic sharpening of inapproximability: Vertex Cover becomes hard within $2 - ε$ (matching the simple 2-approximation), Max-Cut becomes hard within the Goemans-Williamson constant $α_{G W} \approx 0.878$ (matching the SDP algorithm), and every CSP has its approximation threshold determined by semidefinite programming ^{[Arora-Barak Ch. 11]}. The UGC remains open; a disproof would reshape the landscape.

Result 3 (the sliding-scale conjecture). Bellare, Goldwasser, Lund and Russell (1993) conjectured that for every constant $q$ , there exists $c_{q} > 0$ such that for all constants $s < 1$ , $(1, s)$ -gap $q$ -CSP is NP-hard. This would mean that the soundness can be made arbitrarily small while keeping the query complexity constant. Dinur's proof of the PCP theorem via gap amplification (2007) achieves some soundness reduction but not the full sliding scale; achieving it remains a central open problem in complexity theory ^{[Arora-Barak Ch. 11]}.

Synthesis. The PCP theorem is the foundational reason the landscape of approximability is structured rather than chaotic: it creates a universal mechanism for turning computational hardness into approximation hardness, and this builds toward the algorithmic upper bounds of 47.04.08 that complement the lower bounds proven here. The central insight is that the gap between completeness and soundness in a PCP verifier translates directly into the gap between what an approximation algorithm can guarantee and what is information-theoretically possible, and this is exactly the pattern that generalises from MAX-3SAT to every NP optimisation problem via gap-preserving reductions. Putting these together with the interactive proof framework of 47.03.04 and the derandomisation techniques of 47.05.05 yields the full picture: the PCP theorem is the structural backbone connecting computational complexity, proof systems, and approximation algorithms, and its extensions (UGC, sliding scale) push toward the exact boundary of efficient computation.

Full proof set Master

Proposition 1 (gap-3SAT from PCP). If NP = PCP(log n, 1), then for every $ε > 0$ , the $(1, 7/8 + ε)$ -gap-3SAT problem is NP-hard.

Proof. Let $L \in N P$ . By the PCP theorem, $L$ has a $(lo g n, q)$ -PCP verifier $V$ for some constant $q$ . Håstad's transformation produces a $(lo g n, 3)$ -PCP $V^{'}$ for $L$ that reads exactly 3 proof bits and checks their XOR. For each random string $r \in {0, 1}^{c l o g n}$ , define a clause $C_{r}$ on variables $y_{i_{r}}, y_{j_{r}}, y_{k_{r}}$ (the three queried positions): $C_{r} = (y_{i_{r}} \oplus y_{j_{r}} \oplus y_{k_{r}} = b_{r})$ for the appropriate bit $b_{r}$ . The formula $φ = ⋀_{r} C_{r}$ has $m = n^{c}$ clauses.

Completeness: If $x \in L$ , there exists a proof $π$ accepted with probability 1. The assignment $y_{i} = π_{i}$ satisfies every clause $C_{r}$ , so $O P T (φ) = m$ .

Soundness: If $x \in / L$ , every proof $π$ is accepted by $V^{'}$ with probability at most $s$ for some constant $s < 1$ . The Håstad analysis shows $s$ can be made at most $7/8 + ε$ for any desired $ε > 0$ (by choosing the long-code test parameter appropriately). So at most $(7/8 + ε) m$ clauses can be simultaneously satisfied. $□$

Proposition 2 (Vertex Cover inapproximability). There exists a constant $α > 1$ such that Vertex Cover is NP-hard to approximate within factor $α$ .

Proof. By Proposition 1, $(1, 7/8 + ε)$ -gap-3SAT is NP-hard for any $ε > 0$ . Given a 3CNF formula $φ$ with $m$ clauses and $n$ variables, construct a graph $G$ : create a triangle for each clause $C_{j} = (ℓ_{1} \lor ℓ_{2} \lor ℓ_{3})$ with vertices $v_{j, 1}, v_{j, 2}, v_{j, 3}$ , and add an edge between $v_{j, k}$ and $v_{j^{'}, k^{'}}$ whenever they correspond to opposite literals (one is $x_{i}$ and the other is $\overset{x}{ˉ}_{i}$ ). If $φ$ is satisfiable, selecting one true literal per clause gives a vertex cover of size $m$ (pick the two non-true-literal vertices from each triangle). If at most $(7/8 + ε) m$ clauses are satisfiable, then any vertex cover must include at least $α m$ vertices for some $α > 1$ depending on $ε$ , because the contradiction edges force the cover to be large. An $α$ -approximation for Vertex Cover would distinguish the two cases, solving the gap problem. $□$

Connections Master

47.02.03 — NP-completeness provides the baseline: every problem reduced to in this unit is NP-hard to solve exactly, and the PCP theorem adds the approximation layer on top.
47.03.04 — Interactive proofs IP = PSPACE extend to multiprover interactive proofs MIP = NP, which is equivalent to the PCP theorem; the PCP verifier is the single-prover optimisation of the multiprover protocol.
47.03.05 — The PCP theorem itself (NP = PCP(log n, 1)) is the prerequisite machinery; this unit applies it to concrete optimisation problems.
47.04.08 — Approximation algorithms provide upper bounds (Vertex Cover 2-approx, Set Cover $ln n$ -approx) that complement the lower bounds proven here; the gap between upper and lower bounds defines the frontier of the field.
47.05.04 — Randomised approximation schemes (FPRAS) for counting problems face analogous hardness barriers: #P-completeness often blocks efficient exact counting, and the PCP framework determines when approximate counting is possible.

Historical & philosophical context Master

The PCP theorem was proved in two stages. Arora and Safra (1998) established NP = PCP(log n, polylog n), and Arora, Lund, Motwani, Sudan and Szegedy (1998) strengthened this to NP = PCP(log n, 1), earning the Gödel Prize in 2001. Dinur's alternative proof (2007) uses gap amplification via graph powering, providing a combinatorial route to the same result. Håstad (2001) refined the PCP to achieve optimal inapproximability for MAX-3SAT using Fourier analysis of the long code.

The philosophical significance is that approximation is not a universal escape from NP-hardness: some problems have hard walls beyond which no efficient algorithm can reach. This resolved a decades-old question about whether NP-hard optimisation problems could always be tamed by accepting approximate solutions. The answer is nuanced—some can (knapsack admits an FPTAS), some cannot (MAX-3SAT at 7/8, Set Cover at ln n)—and the PCP theorem is the tool that draws the line ^{[Arora-Barak Ch. 11]}.

Bibliography Master

@book{arora2009computational,
  author    = {Arora, Sanjeev and Barak, Boaz},
  title     = {Computational Complexity: A Modern Approach},
  publisher = {Cambridge University Press},
  year      = {2009},
}
@article{hastad2001optimal,
  author  = {H{\aa}stad, Johan},
  title   = {Some Optimal Inapproximability Results},
  journal = {Journal of the ACM},
  volume  = {48},
  number  = {4},
  pages   = {798--859},
  year    = {2001},
}
@article{arora1998proof,
  author  = {Arora, Sanjeev and Lund, Carsten and Motwani, Rajeev and Sudan, Madhu and Szegedy, Mario},
  title   = {Proof Verification and the Hardness of Approximation Problems},
  journal = {Journal of the ACM},
  volume  = {45},
  number  = {3},
  pages   = {501--555},
  year    = {1998},
}
@article{dinur2007pcp,
  author  = {Dinur, Irit},
  title   = {The {PCP} Theorem by Gap Amplification},
  journal = {Journal of the ACM},
  volume  = {54},
  number  = {2},
  year    = {2007},
}
@inproceedings{khot2002unique,
  author    = {Khot, Subhash},
  title     = {On the Power of Unique 2-Prover 1-Round Games},
  booktitle = {Proceedings of the 34th ACM Symposium on Theory of Computing},
  year      = {2002},
  pages     = {767--775},
}

Prerequisites

47.03.05 pending
47.02.03 pending

Tier anchors

beginner: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 11 (why some NP-hard problems resist good approximation algorithms)
intermediate: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 11 (PCP theorem, gap-producing reductions, inapproximability constants)
master: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 11; Arora, Lund, Motwani, Sudan and Szegedy 1998 Proof Verification and the Hardness of Approximation Problems (JACM) (PCP theorem proof, optimal inapproximability via Håstad's 3-bit PCP)

References

Arora, S. and Barak, B. — Computational Complexity: A Modern Approach · Cambridge University Press (2009). Chapter 11 develops hardness of approximation via the PCP theorem, stating that $N P = P C P (lo g n, 1)$ , which asserts that every NP language has a probabilistically checkable proof where the verifier reads only $O (1)$ bits of the proof and uses $O (lo g n)$ random bits; this yields the gap version of 3SAT: given a 3CNF formula $φ$ , it is NP-hard to distinguish $φ$ that is satisfiable from $φ$ where at most a $7/8 + ε$ fraction of clauses can be satisfied simultaneously; this gap is optimal by the random assignment argument. Chapter 11 also covers gap-producing reductions from 3SAT to Vertex Cover (showing Vertex Cover is NP-hard to approximate within factor $1.36$ ), to Max-Clique (within factor $n^{1 - ε}$ ), and to Set Cover (within factor $(1 - ε) ln n$ ).
Håstad, J. — Some Optimal Inapproximability Results · Journal of the ACM 48(4):798--859 (2001). Proves that MAX-3SAT is NP-hard to approximate beyond the factor $7/8 + ε$ for any $ε > 0$ using a 3-bit PCP that performs a long-code test with Fourier analysis; this matches the random-assignment upper bound, establishing optimal inapproximability. Also proves that Max-Clique is hard to approximate within $n^{1 - ε}$ and that Max-LIN-2 is hard beyond ratio $1/2 + ε$ .

Estimated time

beginner: 15m
intermediate: 40m
master: 90m