47.03.05 · theoretical-cs / advanced-complexity

The PCP Theorem: Probabilistically Checkable Proofs and Hardness of Approximation

shipped3 tiersLean: nonepending prereqs

Anchor (Master): Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §11.1-11.5 (Dinur's proof via gap amplification, the original ALMSS proof via low-degree testing and composition, hardness of approximating MAX-3SAT, vertex cover, and clique)

Intuition Beginner

A mathematician submits a proof to a journal. The referee reads every line carefully. This takes a long time. But what if the referee could verify the proof by reading only a few randomly chosen lines?

This sounds impossible. A proof with a single error could be wrong, and the error might be on any line. If the referee reads only three lines out of a thousand, the error could easily be missed.

The PCP theorem says it is possible — for a specific kind of proof system. The trick is that the proof is specially encoded. Instead of the usual linear format, the proof is written so that any error is "spread out" over many locations. A single logical mistake in the argument causes inconsistencies throughout the encoded proof. So reading a few random locations has a good chance of catching any error.

Think of it as a holographic proof. In a hologram, every piece contains information about the whole image. Similarly, every small piece of a PCP proof contains partial information about the whole argument. Checking a few pieces suffices because a false proof has inconsistencies everywhere.

More precisely: for any NP problem, there is a way to write proofs such that a verifier using logarithmically many coin flips and reading only a constant number of bits (say, 3) can distinguish correct proofs from incorrect ones with high probability. This constant number of queries does not depend on the input size.

The PCP theorem has a dramatic consequence for approximation. It implies that for many optimisation problems, finding even an approximate solution is as hard as finding the exact solution. For example, there is no polynomial-time algorithm that approximates the maximum number of satisfiable clauses in a 3SAT formula within a factor of $7/8 + ϵ$ (for any $ϵ > 0$ ) unless P = NP.

Visual Beginner

The PCP verification process:

          Proof π (long string of bits)
          ┌──────────────────────────────────────────┐
          │ 0 1 1 0 0 1 1 0 1 0 0 1 1 0 1 0 ...     │
          └──────────────────────────────────────────┘
                    ↑     ↑  ↑
                    │     │  │
        Verifier V reads only 3 bits (using random coins to choose which)

  Coins: r = 0110...  →  positions 47, 203, 891
  Check: does the constraint on those 3 bits hold?

Property	Description
Randomness	$O (lo g n)$ coin flips (polynomially many possible random strings)
Queries	$O (1)$ bits of the proof (constant, independent of input size)
Completeness	If $x \in L$ , there exists $π$ accepted with probability 1
Soundness	If $x \in / L$ , every $π$ is rejected with probability $\geq 1/2$

The gap view of hardness of approximation:

MAX-3SAT optimum fraction of satisfiable clauses:

  Yes-instance:    ≥ 7/8 + ε of clauses can be satisfied
  No-instance:     ≤ 7/8 of clauses can be satisfied

  Gap of ε between yes and no instances
  → Approximating within 7/8 + ε is NP-hard

Worked example Beginner

Consider the connection between the PCP theorem and MAX-3SAT hardness.

MAX-3SAT asks: given a 3CNF formula, what fraction of clauses can be simultaneously satisfied? A random assignment satisfies $7/8$ of clauses in expectation (each clause has 3 literals, fails with probability $1/8$ ).

The PCP theorem implies that there exists $ϵ > 0$ such that distinguishing between "all clauses satisfiable" and "at most $7/8 + ϵ$ clauses satisfiable" is NP-hard.

To see why, start with a 3SAT instance $ϕ$ . By the PCP theorem, there is an encoding that creates a new 3SAT-like instance $ϕ^{'}$ where:

If $ϕ$ is satisfiable, then $ϕ^{'}$ has an assignment satisfying $\geq 7/8 + ϵ$ fraction of clauses.
If $ϕ$ is unsatisfiable, then every assignment satisfies $\leq 7/8$ fraction of clauses.

If there were a polynomial-time algorithm approximating MAX-3SAT within $7/8 + ϵ$ , it could distinguish these two cases and hence decide 3SAT. This would imply P = NP.

This is the "gap" version of the PCP theorem: it creates a gap between the best achievable in yes-instances and no-instances, and this gap makes approximation NP-hard.

Check your understanding Beginner

Formal definition Intermediate+

Definition (PCP class). $PCP [r (n), q (n)]$ is the class of languages $L$ for which there exists a polynomial-time probabilistic verifier $V$ such that:

On input $x$ of length $n$ , $V$ uses at most $O (r (n))$ random bits.
$V$ queries at most $O (q (n))$ bits of the proof $π$ .
Completeness: If $x \in L$ , there exists $π$ such that $Pr_{R} [V^{π} (x; R) = 1] = 1$ .
Soundness: If $x \in / L$ , then for every $π$ , $Pr_{R} [V^{π} (x; R) = 1] \leq 1/2$ .

Theorem (PCP theorem). $NP = PCP [lo g n, 1]$ .

The inclusion $PCP [lo g n, 1] \subseteq NP$ is the easier direction: the verifier uses $O (lo g n)$ random bits, so there are only polynomially many possible random strings. An NP verifier can simulate all of them deterministically and accept iff they all accept.

The inclusion $NP \subseteq PCP [lo g n, 1]$ is the deep direction. Two proofs exist:

Original proof (ALMSS 1998). Encode the NP computation as a low-degree polynomial (arithmetisation), and use self-testing and self-correction techniques from program checking to verify the polynomial with few queries. The proof uses algebraic techniques from coding theory and the theory of low-degree extensions.

Dinur's proof (2007). Start with a constraint graph (a graph where edges represent constraints on vertex labels) and iteratively amplify the gap between satisfiable and unsatisfiable instances by graph powering and composition. Each step increases the fraction of violated constraints in the no-case while preserving satisfiability in the yes-case.

Theorem (equivalent gap formulation). The PCP theorem is equivalent to: there exists $ϵ > 0$ such that given a 3CNF formula $ϕ$ , it is NP-hard to distinguish:

(Yes) $ϕ$ is satisfiable.
(No) Every assignment satisfies $< 1 - ϵ$ fraction of clauses.

Proof of equivalence. PCP $\Rightarrow$ gap: the PCP verifier for SAT produces a constraint system on $O (1)$ variables per constraint, which can be converted to a 3CNF formula with a gap. Gap $\Rightarrow$ PCP: a gap instance provides the separation needed for the PCP soundness condition; the proof consists of the assignment, and the verifier checks random constraints. $□$

Counterexamples to common slips

"The PCP theorem proves that NP proofs can be checked in constant time." The verifier runs in polynomial time (to compute which bits to query based on the randomness). Only the number of proof bits read is constant. The total running time is polynomial.
"Soundness 1/2 is the best possible." The soundness can be reduced to any constant less than 1 by repeating the PCP verification $O (1)$ times (using additional random bits but still $O (lo g n)$ total).
"The PCP theorem only applies to SAT." The PCP theorem applies to every NP language. SAT is used as the starting point because it is NP-complete, but the theorem is a characterisation of the entire class NP.

Key theorem with proof Intermediate+

Theorem (NP $\subseteq$ PCP[ $lo g n$ , 1]). Every NP language has a probabilistically checkable proof with $O (lo g n)$ randomness and $O (1)$ queries.

Proof sketch (Dinur's approach).

Step 1 (constraint graph formulation). An NP computation can be encoded as a constraint graph $G = (V, E, Σ, Φ)$ where each vertex $v$ has a label $σ (v) \in Σ$ and each edge $(u, v)$ carries a constraint $ϕ_{uv} \in Φ$ on $(σ (u), σ (v))$ . SAT maps to: is there a labelling satisfying all constraints?

Step 2 (gap creation). Define $UNSAT (G)$ as the minimum fraction of unsatisfied edges over all labellings. If $G$ is satisfiable, $UNSAT (G) = 0$ . If $G$ is unsatisfiable, $UNSAT (G) > 0$ (but possibly very small).

Step 3 (gap amplification by powering). The graph power $G^{t}$ replaces each vertex by a neighbourhood of radius $t$ , and each edge of $G^{t}$ carries a constraint on the labels of all vertices in the two neighbourhoods. If $UNSAT (G) = ϵ$ , then $UNSAT (G^{t}) \geq C_{t} \cdot ϵ$ where $C_{t} \to 1$ as $t \to \infty$ . This amplifies a small gap to a constant gap.

Step 4 (alphabet reduction). The powering step increases the alphabet size. A composition step (using an "inner" PCP as a gadget) reduces the alphabet back to a constant without losing the gap.

Step 5 (iteration). Repeat gap amplification and alphabet reduction $O (1)$ times until $UNSAT (G) \geq ϵ_{0}$ for a constant $ϵ_{0} > 0$ in the no-case.

Step 6 (PCP construction). The final constraint graph with constant gap $ϵ_{0}$ gives a PCP: the proof is the vertex labelling, the verifier picks a random edge, reads the labels of its two endpoints ( $O (1)$ bits), and checks the constraint. If the graph is satisfiable, all edges pass. If not, a random edge fails with probability $\geq ϵ_{0}$ . $□$

Bridge. The PCP theorem builds toward the entire theory of hardness of approximation as the natural quantitative refinement of NP-completeness: the central insight is that NP-hardness does not merely prevent finding exact optima but also prevents finding good approximations for many problems, and this is exactly what makes the PCP theorem the most powerful tool in the theory of approximation algorithms. This appears again in 47.02.03 where the NP-completeness of 3SAT, Clique, and Vertex Cover is the starting point, and in 47.03.03 where the random-restriction techniques used in circuit lower bounds share a common probabilistic methodology with PCP constructions. The foundational reason the PCP theorem works is that algebraic encoding (low-degree polynomials) and combinatorial amplification (gap amplification) provide complementary methods for spreading information across a proof, and putting these together with the gap formulation shows that approximation hardness is not an isolated phenomenon but a structural property of NP-complete optimisation problems.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Show that $NP \subseteq PCP [poly (n), 0]$ .

Answer

A PCP verifier with $poly (n)$ randomness and 0 queries does not read the proof at all. With $2^{poly (n)}$ possible random strings, the verifier's acceptance condition defines a polynomially checkable property of the input. But with 0 queries, the verifier's output depends only on $x$ and $R$ , not on $π$ . This means the proof is irrelevant, and the language must be decidable by a polynomial-time randomised algorithm with polynomial randomness — which is just $BPP$ . So $PCP [poly (n), 0] = BPP$ . Since $NP \subseteq BPP$ is not known, this containment does not follow directly. The correct statement is $PCP [poly (n), 0] = P$ (since with 0 proof queries, the proof cannot help, and the verifier just decides $x$ deterministically after fixing $R$ ; but the completeness/soundness conditions force the language to be in P). Actually, with 0 queries, the verifier must deterministically accept or reject based on $R$ alone. For completeness, some $R$ makes it accept; for soundness, no $R$ makes it accept for $x \in / L$ . So $PCP [poly (n), 0] = P$ .

Exercise 4 (medium, symbolic).

Prove that if MAX-3SAT can be approximated within factor $α > 7/8$ in polynomial time, then P = NP.

Hint

Use the PCP theorem to create a gap 3SAT instance where yes-instances are fully satisfiable and no-instances have $\leq 7/8 + ϵ$ fraction satisfiable.

Answer

By the PCP theorem (gap formulation), there exists $ϵ > 0$ such that given a 3CNF formula, it is NP-hard to distinguish (1) all clauses satisfiable from (2) every assignment satisfies $< 7/8 + ϵ$ fraction of clauses. Suppose there is a polynomial-time $α$ -approximation for MAX-3SAT with $α > 7/8$ . Choose $ϵ < α - 7/8$ . On a yes-instance, the approximation finds an assignment satisfying $\geq α \cdot 1 > 7/8 + ϵ$ fraction. On a no-instance, the optimum is $< 7/8 + ϵ$ , so the approximation returns $< α (7/8 + ϵ) < 7/8 + ϵ$ (for appropriate $ϵ$ ). The approximation algorithm can thus distinguish yes from no instances, solving an NP-hard problem in polynomial time. So P = NP.

Exercise 6 (hard, symbolic).

Prove the easier direction: $PCP [lo g n, 1] \subseteq NP$ .

Answer

Let $L \in PCP [lo g n, 1]$ with verifier $V$ . The NP machine for $L$ works as follows on input $x$ of length $n$ . The certificate is the proof string $π$ of length $poly (n)$ . The NP verifier enumerates all $2^{O (l o g n)} = n^{O (1)}$ possible random strings $R$ . For each $R$ , it simulates $V (x; R)$ , reading the same $O (1)$ bits of $π$ that $V$ would read. It accepts iff $V$ accepts for every $R$ .

Completeness: if $x \in L$ , the PCP completeness guarantees a proof $π$ accepted on all $R$ , so the NP verifier accepts.

Soundness: if $x \in / L$ , the PCP soundness guarantees that every $π$ is rejected on at least half the random strings. So the NP verifier (which checks all random strings) rejects.

The running time is polynomial: $n^{O (1)}$ random strings, each simulation takes polynomial time.

Exercise 7 (hard, symbolic).

Describe Dinur's gap amplification step: given a constraint graph $G$ with $UNSAT (G) \geq ϵ$ , show how powering increases the unsat value.

Answer

The $t$ -th power $G^{t}$ is defined as follows. Each vertex $v$ of $G^{t}$ corresponds to a ball of radius $t /2$ around $v$ in $G$ (the set of vertices at distance $\leq t /2$ from $v$ ). An edge $(u, v)$ in $G^{t}$ exists if the $t /2$ -balls around $u$ and $v$ overlap or are adjacent. The constraint on this edge depends on the labels of all vertices in both balls.

If $UNSAT (G) = ϵ$ (a fraction $ϵ$ of edges are violated by any labelling), then for $G^{t}$ the unsat value increases. The key claim is: $UNSAT (G^{t}) \geq min (1, C \cdot t \cdot ϵ)$ for some constant $C$ .

Intuition: if a fraction $ϵ$ of edges are violated in $G$ , then in a $t$ -step random walk from any vertex, the expected number of violated edges is $ϵ t$ . In $G^{t}$ , each "super-edge" tests the constraints on a $t$ -neighbourhood, and violations in $G$ propagate to violations in $G^{t}$ . The amplification factor is roughly $t$ (not $t$ , because correlated violations may cluster).

By choosing $t$ large enough (but still constant), the unsat value can be boosted from arbitrarily small $ϵ$ to a constant $ϵ_{0}$ .

Exercise 8 (hard, symbolic).

State and prove the composition lemma used in Dinur's proof: how does composing an "outer" PCP with an "inner" PCP reduce the alphabet size?

Answer

Composition lemma (informal). If a constraint system $G$ has alphabet $Σ$ of size $∣Σ∣ = s$ , and there exists an "inner" PCP for testing whether a function $f : [n] \to Σ$ satisfies a constraint $ϕ$ using alphabet size 2 and query complexity $q$ , then $G$ can be replaced by a new constraint system $G^{'}$ with alphabet size 2, query complexity $q$ , and $UNSAT (G^{'}) \geq c \cdot UNSAT (G)$ for some constant $c$ .

Proof idea. Each vertex $v$ of $G$ has a label $σ (v) \in Σ$ . Replace $σ (v)$ by its encoding under the inner PCP: a long binary string $\overset{σ}{^} (v)$ such that the constraint $ϕ$ on edge $(u, v)$ can be verified by the inner PCP reading $q$ bits of $\overset{σ}{^} (u)$ and $\overset{σ}{^} (v)$ . The inner PCP's soundness ensures that if $ϕ$ is violated, the inner verification rejects with constant probability. This preserves the gap while reducing the alphabet from $Σ$ to ${0, 1}$ . The key technical detail is ensuring the encoding is "locally testable": the inner PCP can detect violations with few queries.

Lean formalization Intermediate+

Mathlib has no formalisation of the PCP theorem, probabilistically checkable proofs, or hardness-of-approximation results. The foundational gap is the absence of a Complexity.PCP class definition, a formalised gap-amplification argument, and any hardness-of-approximation result for specific problems. The PCP theorem's proof is one of the longest and most technical in complexity theory, making it a significant formalisation challenge. This unit ships without a lean_module.

Advanced results Master

Three frontiers extend the PCP theorem.

Theorem 1 (Håstad's optimal 3-bit PCP). For any $ϵ > 0$ , $NP = PCP_{1, 7/8 + ϵ} [lo g n, 3]$ , where the subscripts indicate completeness 1 and soundness $7/8 + ϵ$ . The verifier reads exactly 3 bits of the proof and accepts iff they satisfy a linear equation mod 2 ^{[Arora & Barak §11.5]}.

This is optimal: 3 bits is the minimum needed for a meaningful PCP, and $7/8$ is the threshold for MAX-3SAT (since a random assignment satisfies $7/8$ of clauses).

Theorem 2 (unique games conjecture). Khot's Unique Games Conjecture (2002) states that a specific constraint satisfaction problem (where each constraint is a bijection on the labels) is NP-hard to approximate. If true, it gives tight hardness-of-approximation results for many problems: VERTEX-COVER cannot be approximated within $2 - ϵ$ , MAX-CUT cannot be approximated within $16/17 + ϵ$ , etc.

The UGC is a strengthened version of the PCP theorem that, if true, would resolve the approximability of many fundamental optimisation problems.

Theorem 3 (2-to-1 theorem). Dinur, Khot, Kindler, Minzer, and Safra (2018) proved that a variant of the label-cover problem with 2-to-1 constraints is NP-hard. This gives hardness of approximation results intermediate between the PCP theorem and UGC, including the result that approximating vertex cover within $2 - ϵ$ is NP-hard.

Synthesis. The PCP theorem is the foundational reason that NP-completeness has quantitative consequences for approximation: the central insight is that the gap between completeness and soundness in a PCP directly translates to a hardness-of-approximation result for an optimisation problem, and this is exactly what makes the PCP theorem the bridge between computational complexity and combinatorial optimisation. This builds toward the unique games conjecture which promises to resolve the approximability of virtually every fundamental NP-hard problem, and appears again in 47.02.03 where the NP-complete problems serve as the starting point for gap-producing reductions. The generalises from the qualitative statement "this problem is hard" to the quantitative statement "this problem is hard to approximate within factor $α$ ," and putting these together with Håstad's optimal result shows that the PCP framework gives matching upper and lower bounds for the approximability of MAX-3SAT.

Full proof set Master

Proposition 1 (PCP[ $lo g n$ , 1] $\subseteq$ NP). Every language in $PCP [lo g n, 1]$ is in NP.

Proof. Let $L \in PCP [lo g n, 1]$ with verifier $V$ . The certificate is the proof string $π$ . The NP verifier enumerates all $2^{O (l o g n)} = n^{O (1)}$ random strings $R_{1}, \dots, R_{m}$ . For each $R_{i}$ , it simulates $V (x; R_{i})$ on the same proof $π$ , reading $O (1)$ bits. It accepts iff $V$ accepts for all $R_{i}$ .

If $x \in L$ : by completeness, there exists $π$ accepted on all $R_{i}$ . NP verifier accepts.

If $x \in / L$ : by soundness, for every $π$ , $V$ rejects on $\geq 1/2$ of the $R_{i}$ . The NP verifier checks all $R_{i}$ and rejects. $□$

Proposition 2 (gap-to-hardness reduction). If it is NP-hard to distinguish 3CNF formulas where all clauses are satisfiable from those where $< 7/8 + ϵ$ are satisfiable, then approximating MAX-3SAT within $7/8 + ϵ$ is NP-hard.

Proof. Let $ϕ$ be a 3CNF formula. Use the gap-producing reduction to create $ϕ^{'}$ . If $ϕ$ is satisfiable, $ϕ^{'}$ is fully satisfiable (value 1). If $ϕ$ is unsatisfiable, $ϕ^{'}$ has value $< 7/8 + ϵ$ . A $(7/8 + ϵ)$ -approximation for MAX-3SAT would return a value $> 7/8 + ϵ$ in the first case and $< 7/8 + ϵ$ in the second, distinguishing them. This decides SAT in polynomial time, so P = NP. $□$

Connections Master

47.02.02 — The Cook-Levin theorem and NP-completeness of SAT provide the starting point for the PCP construction.
47.02.03 — Classic NP-complete problems (MAX-3SAT, Clique, Vertex Cover) are the targets of hardness-of-approximation results derived from the PCP theorem.
47.03.03 — The random-restriction techniques used in circuit lower bounds share probabilistic methodology with PCP constructions (randomness for amplification).
47.03.04 — Interactive proofs (IP = PSPACE) and PCP both use randomised verification; IP extends to PSPACE while PCP characterises NP.
47.04.04 — Bipartite matching (in P) contrasts with the NP-hard approximability of problems like vertex cover on general graphs.

Historical & philosophical context Master

The PCP theorem was proved by Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy in 1992 (published in JACM 1998). Their proof used algebraic techniques: arithmetising NP computations as low-degree polynomials and using self-testing/correcting methods from the theory of program checking. This work earned them the Gödel Prize in 2001 ^{[Arora & Barak §11.2]}.

Irit Dinur's 2007 proof was a major simplification. She replaced the algebraic machinery with a purely combinatorial gap-amplification argument, making the PCP theorem accessible to a wider audience. Her proof iteratively amplifies the unsatisfiability gap of a constraint graph by graph powering and composition, and was recognised with the Michael O. Rabin Prize.

The PCP theorem resolved a question posed by Feige, Goldwasser, Lovász, Safra, and Szegedy (1991) who first showed the connection between interactive proof systems and hardness of approximation. The philosophical significance is that the difficulty of NP-complete problems extends beyond finding exact solutions: even finding good approximations is intractable, and the quality of approximation that is achievable is precisely quantified by the PCP's soundness parameter.

Johan Håstad's 2001 result gave the optimal 3-bit PCP with soundness $7/8 + ϵ$ , which is the strongest possible for any 3-query PCP testing linear equations. This matched the simple random-assignment algorithm that achieves $7/8$ for MAX-3SAT, giving a tight result.

Bibliography Master

@book{arora2009computational,
  author    = {Arora, Sanjeev and Barak, Boaz},
  title     = {Computational Complexity: A Modern Approach},
  publisher = {Cambridge University Press},
  year      = {2009},
}
@article{almss1998proof,
  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 third},
  number  = {2},
  pages   = {1--44},
  year    = {2007},
}
@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{khot2002unique,
  author  = {Khot, Subhash},
  title   = {On the Power of Unique 2-Prover 1-Round Games},
  journal = {Proceedings of the 34th ACM Symposium on Theory of Computing},
  pages   = {767--775},
  year    = {2002},
}

Prerequisites

47.03.04 pending
47.02.02 pending

Tier anchors

beginner: Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §11.1 (NP proofs that can be verified by reading only a constant number of bits, the PCP theorem as a characterisation of NP)
intermediate: Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §11.1-11.3 (formal PCP definition, the PCP theorem NP = PCP[O(log n), O(1)], the gap-intuition for hardness of approximation)
master: Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §11.1-11.5 (Dinur's proof via gap amplification, the original ALMSS proof via low-degree testing and composition, hardness of approximating MAX-3SAT, vertex cover, and clique)

References

Arora, S. & Barak, B. — Computational Complexity: A Modern Approach · Cambridge University Press (2009). Section 11.1 defines probabilistically checkable proofs: $PCP [r (n), q (n)]$ is the class of languages $L$ for which there exists a polynomial-time verifier $V$ that, on input $x$ of length $n$ , uses $O (r (n))$ random bits and queries $O (q (n))$ bits of a proof $π$ , such that (1) if $x \in L$ , there exists $π$ with $Pr [V^{π} (x) = 1] = 1$ (completeness), and (2) if $x \in / L$ , then for every $π$ , $Pr [V^{π} (x) = 1] \leq 1/2$ (soundness). The PCP theorem (Arora, Lund, Motwani, Sudan, Szegedy 1998; Dinur 2007) states $NP = PCP [lo g n, 1]$ : every NP language has a proof that can be verified with $O (lo g n)$ random bits and $O (1)$ proof queries. Section 11.3 shows the equivalence between the PCP theorem and hardness of approximation: MAX-3SAT cannot be approximated within a factor of $7/8 + ϵ$ in polynomial time unless P = NP.

Estimated time

beginner: 15m
intermediate: 40m
master: 75m