Questions: PCP Theorem and Hardness of Approximation

Question 1

The PCP theorem states that NP = PCP(log n, 1). What do the parameters log n and 1 represent?

• A. The verifier uses log n proof bits and 1 random bit
• B. The verifier uses O(log n) random bits and reads O(1) bits of the proof
• C. The proof has length log n and the verifier runs in time O(1)
• D. The verifier makes log n passes over the proof, each reading 1 bit

Answer: (B)

PCP(r(n), q(n)) denotes the class of languages decidable by a probabilistic verifier using O(r(n)) random bits and reading O(q(n)) bits of a (polynomially long) proof. The PCP theorem says NP = PCP(log n, 1): for any NP language, there exists a proof format where the verifier uses O(log n) random coins (to select which proof bits to inspect) and reads only O(1) proof bits, yet achieves soundness error at most 1/2. The O(log n) random bits mean poly(n) possible verification patterns, which is essential — it keeps the proof polynomial length. The O(1) query complexity is the surprising part: constant queries suffice to probabilistically verify any NP statement.

Question 2

The PCP theorem implies that it is NP-hard to distinguish between satisfiable 3SAT instances and instances where at most a 7/8 fraction of clauses can be satisfied.

• T. True
• F. False

Answer: True

This is the gap-introducing reduction that follows from the PCP theorem. Hastad's 1997 result shows that for any epsilon > 0, it is NP-hard to distinguish between 3SAT instances that are fully satisfiable and those where at most (7/8 + epsilon) fraction of clauses can be satisfied. Since a random assignment satisfies 7/8 of all 3SAT clauses in expectation, this means the trivial random algorithm is essentially optimal for MAX-3SAT unless P = NP. The PCP theorem provides the framework for this gap: it converts the YES/NO distinction of NP-completeness into a quantitative gap in the optimization value.

Question 3

Explain how Dinur's proof of the PCP theorem works at a high level, and why gap amplification is the central technique.

Model answer: Dinur's proof starts with a standard NP verification as a constraint graph (vertices = variable assignments, edges = constraints). Satisfiable instances have assignments violating 0 constraints; unsatisfiable instances violate at least 1. The goal is to amplify this gap: transform the graph so satisfiable instances still have 0 violations but unsatisfiable instances violate a CONSTANT FRACTION of constraints. Dinur achieves this through O(log n) iterations of: (1) graph powering — replace G with G^t to make it an expander, propagating constraint violations to neighbors, (2) alphabet reduction — compose with a 'gadget' PCP to keep the alphabet size bounded while preserving the gap. Each iteration roughly squares the fraction of violated constraints (from delta to ~delta^(1/2) closer to constant). After O(log n) iterations, the gap reaches a constant, yielding PCP(log n, 1).

The key insight of Dinur's proof is that gap amplification can be achieved combinatorially through graph operations, avoiding the algebraic machinery (low-degree tests, linearity tests) of the original Arora-Lund-Motwani-Sudan-Szegedy / Arora-Safra proof. Each iteration is a polynomial-time reduction that preserves satisfiability while amplifying the unsatisfiability gap.

Question 4

Why can't we use the PCP theorem to prove hardness of approximation for problems in P?

• A. The PCP theorem only applies to maximization problems
• B. The PCP theorem requires the underlying decision problem to be NP-hard; for problems in P, the gap created by a PCP reduction can be efficiently resolved
• C. The PCP theorem assumes the Unique Games Conjecture
• D. Problems in P have no meaningful approximation ratio

Answer: (B)

PCP-based inapproximability works by reducing an NP-hard problem to a gap version of the target problem: if you could approximate the target within the gap, you could decide the NP-hard problem. For problems already in P, this reduction is vacuous — you can solve them exactly in polynomial time, so there is no hardness to reduce from. The PCP theorem transforms the NP-completeness of SAT into a gap (between satisfiable and far-from-satisfiable instances), and this gap transfers to other problems via gap-preserving reductions. No NP-hardness means no gap to transfer.

Question 5

The Unique Games Conjecture (UGC) strengthens the PCP theorem. If true, what additional inapproximability results does it yield?

Model answer: The UGC asserts that for any epsilon > 0, it is NP-hard to decide whether a unique-label-cover instance has value >= 1 - epsilon or <= epsilon. If true, it implies: (1) MAX-CUT cannot be approximated beyond the Goemans-Williamson ratio of ~0.878 (matching the SDP-based algorithm), (2) Vertex Cover cannot be approximated beyond factor 2 - epsilon (matching the LP rounding), (3) every constraint satisfaction problem's approximation threshold is determined by the SDP integrality gap. The UGC would essentially show that for a wide class of problems, the best known algorithms (typically LP/SDP-based) are already optimal.

The UGC, proposed by Khot in 2002, remains unproven but has transformed the landscape of approximation algorithms by providing conditional optimality proofs for many algorithms whose approximation ratios seemed improvable. It also inspired Dinur's combinatorial approach to gap amplification.