A conventional verifier may read a whole certificate. A probabilistically checkable proof can be much longer than the portion inspected: the verifier uses a few random bits to choose a few positions, then decides whether the bits it sees are locally consistent. The remarkable part is not that a true assertion has a proof, but that every purported proof of a false assertion fails a randomly chosen test with noticeable probability. This distinction turns verification error into an optimization gap.
Local access and global correctness
Definition 10.1.1
(Probabilistically checkable proof verifier)
A probabilistically checkable proof verifier is a randomized polynomial-time machine with random access to a binary proof string. On an input of length , its randomness budget bounds the number of fair random bits it uses, and its query budget bounds the number of proof positions it reads. The position chosen for a later query may depend on earlier answers unless a nonadaptive convention is explicitly stated. Completeness means every yes-instance has a proof accepted with the specified high probability; soundness means every proof of a no-instance is accepted with at most the specified lower probability.
The proof is fixed before the random coins are chosen. It may depend on the input, but it cannot choose new values after learning which positions are queried. Otherwise the verifier would be interacting with an adaptive prover rather than inspecting one fixed proof. The proof is not assumed honest in the soundness condition. A correct argument bounds the acceptance probability for every possible proof string, including ones that do not encode a meaningful assignment.
For random bits and queries, the notation describes the corresponding verifier classes under fixed completeness and soundness constants, commonly perfect completeness and soundness at most . The verifier's time is polynomial, and addresses have polynomial length. With random bits there are polynomially many possible random strings; if the number of queries is constant, each string selects only a constant number of positions. Random access is an explicit resource convention: moving a physical tape head to a distant position is not being charged as if the verifier had a sequential tape.
Proposition 10.1.2
(Removing adaptivity from a constant number of queries)
Let be a verifier that makes at most binary queries for every input and random string. Then there is a nonadaptive verifier that uses the same random bits and at most queries, and accepts every fixed proof with exactly the same probability as . If is a constant, so is .
Proof
(Unfolding the query tree)
Fix the input and the verifier's random string. If it makes at most binary queries, its possible query-and-answer histories form a binary tree with at most query nodes. A nonadaptive verifier can compute every position appearing in this tree, read those positions at once, and then simulate the original path using the answers. Repeated positions are read consistently from the same fixed proof. The tree is built from the verifier’s code, the input and its fixed coins, not from a proposed proof. Branches inconsistent with the answers actually read are discarded during the simulation. When is a constant, the new query bound is still a constant and the acceptance probability on every fixed proof is unchanged.
Proof X-ray
What the query tree is built from
The argument turns on what the tree is made of. It uses only the verifier's code, the input and the fixed coins, so it is the same for every proof; this is why the positions can all be written down before any proof bit is read, and why acceptance probability is preserved for each fixed proof separately. Discarding branches contradicted by the answers is what keeps the simulation faithful, because only one root-to-leaf path is real. The price is the size of the tree: is a constant when is, so allowing adaptivity does not change the constant-query class, but it is exponential in , so the same conversion need not preserve a query budget that grows with the input.
Why sampling alone is insufficient
For this sampling experiment, take Boolean constraints, with an integer . Uniformly choosing a constraint then uses exactly fair bits; exact uniform sampling for arbitrary would require an additional implementation argument. Consider a proposed assignment to these constraints. A verifier could choose one constraint uniformly, read the variables in it, and accept if it is satisfied. If the assignment satisfies every constraint, acceptance is certain. If it violates a fraction , the rejection probability is exactly . This test has soundness at most only when every candidate assignment violates at least a fixed positive fraction of constraints.
Concept lensCombinatorial
A nonadaptive verifier as a family of constraints
Suppose the test is nonadaptive and uses random bits. Each random string then names at most proof positions and a predicate on them, a constraint . For a fixed proof , the acceptance probability is exactly the fraction of the constraints that satisfies. Soundness says that no proof satisfies more than a fixed fraction of them when the instance is false, which is a gap statement about constraints.
Worked example 10.1.3
(One violated clause can be hard to notice)
For with an integer , take the contradictory pair of one-literal clauses and and add copies of the always-true clause . The formula is unsatisfiable. Nevertheless either value of satisfies exactly one contradictory clause and all the padded clauses, so a uniform random clause test rejects with probability only . As grows, that probability tends to zero. Unsatisfiability alone does not supply a constant soundness gap.
Worked example 10.1.4
(A small formula with a genuine gap)
Consider the four clauses , , and . Each of the four assignments to falsifies exactly one of them, so the formula is unsatisfiable and every assignment has value . A uniformly chosen clause is violated with probability regardless of the supplied assignment. If the same fixed assignment is checked on three independent choices and all three must pass, the acceptance probability is . This example has a constant gap, but it does not show how to convert every unsatisfiable formula into one with a constant gap; that is the hard general construction.
A PCP construction changes the representation of the proof and the tests so that a false assertion cannot be made nearly consistent with all local checks. A proof bit may describe redundant encoded information rather than one original variable. The challenge is to enforce global consistency using only local views; simply adding random sampling to an arbitrary certificate does not solve that challenge.
The PCP theorem as a stated dependency
Theorem 10.1.5
(PCP theorem, standard form)
with perfect completeness and soundness at most , under the random-access and polynomial-time conventions above.
We state the difficult direction of this theorem without proof. It constructs a locally checkable encoding and tests with the promised gap. The reverse inclusion has a useful elementary explanation: a polynomial-time verifier reads only polynomially long addresses, so a proof can be represented by its relevant polynomially many queried bits when there are only polynomially many random strings and constantly many queries. An NP machine guesses those bits and checks all random strings, accepting exactly when their acceptance fraction meets the verifier's completeness threshold. A fully formal version must handle adaptive queries by including every position reached along possible query-answer paths; a constant query bound leaves only a constant number of such paths per random string. The theorem itself is far deeper than this counting observation.
Common mistake
(Reading the theorem as proof recovery)
The theorem is not a claim that a verifier can recover a whole proof from a few bits. Randomness makes a dishonest proof likely to fail a test; acceptance is a probabilistic guarantee about correctness of the claimed instance. A particular random test may accept a false instance, and the soundness bound permits that.
From a gap to an approximation question
Definition 10.1.6
(Value and optimum of a 3-CNF formula)
For a 3-CNF formula with clauses, each containing at most three literals (shorter clauses can be padded by repeated literals), define the value of an assignment as the fraction of clauses it satisfies, and let be the largest such fraction. The maximum is taken over assignments to all variables, and the value of an actual assignment can be computed in polynomial time. A satisfiable formula has optimum ; an unsatisfiable formula may have optimum close to , as the padded example showed.
We use the following gap form of PCP hardness without proof.
Theorem 10.1.7
(Gap form of PCP hardness)
There is a fixed rational constant and a polynomial-time reduction that maps each 3-CNF formula to a 3-CNF formula such that: if is satisfiable, then is satisfiable; if is unsatisfiable, then every assignment satisfies at most a fraction of the clauses of .
Any positive gap can be weakened to such a rational gap, making the thresholds computable constants. This is an additional nontrivial theorem, not a consequence of merely sampling original clauses. The construction and its relation to the PCP theorem are outside this unit.
Proposition 10.1.8
(A gap rules out a polynomial approximation scheme)
Assume the stated gap theorem and . Then there is no polynomial-time approximation scheme for maximizing the fraction of satisfied clauses of 3-CNF formulas. Here a scheme must, for every fixed , return in polynomial time an actual assignment satisfying at least .
Proof
(Proof by distinguishing the two cases)
Suppose such a scheme exists. Fix the constant and use its polynomial-time algorithm for this value. Given a 3-SAT formula, form the gap reduction's output and run the approximation algorithm. Evaluate the returned assignment's fraction of satisfied clauses.
If the original formula is satisfiable, , so the returned assignment has value at least . If the original formula is unsatisfiable, every assignment has value at most , including the returned one. Since , comparing the value with a threshold strictly between them decides 3-SAT in polynomial time. By NP-completeness of 3-SAT, used here without proof, this would imply , contrary to the hypothesis.
The theorem does not assert that MAX-3SAT has no useful approximation algorithm. It rules out a family that gets arbitrarily close to the optimum under the stated assumptions. Nor does it say that every single 3-CNF instance is difficult: the reduction establishes a worst-case barrier for a uniform algorithm that must handle all instances.
Worked example 10.1.9
(A numerical gap decision)
Suppose, only for illustration, that a reduction had gap . A scheme run with would produce value at least on a yes-output, while every assignment has value at most on a no-output. The threshold separates these cases. This numerical example illustrates the proof; it does not claim that the cited theorem's constant is exactly .
Common mistake
(A near-optimal value is not an exact answer)
For an arbitrary unsatisfiable formula, an approximation algorithm may output a value extremely close to ; a satisfiable formula may also receive a value below because the algorithm is approximate. The decision procedure above works because the reduction creates a fixed gap, and because the returned assignment's value can be checked, not because approximation automatically decides satisfiability.
Randomness, amplification, and fixed proofs
If a verifier independently repeats a constant-query test and rejects when any test rejects, a false proof accepted with probability at most in one run is accepted with probability at most after independent runs. Perfect completeness remains perfect. The number of queries grows by a factor of and the random-bit count grows likewise; for fixed both asymptotic bounds in the PCP theorem remain and . This calculation applies to each fixed proof separately. It does not license the proof to change after observing the verifier's coins.
Worked example 10.1.10
(Repeating a local consistency check)
Suppose every proof of a false instance passes one test with probability at most . Three independent tests accept the proof only when all three pass, which has probability at most . A correct proof accepted by every test is still accepted with probability .
The next example shows that the independence of the repetitions is essential.
Counterexample mode
Reusing the same coins is not amplification
Claim: repeating a test three times with the same random string lowers the acceptance probability of a false proof from to . Take a verifier with one random bit and a fixed proof of a false instance that passes the test when and fails when , so it is accepted with probability exactly . If all three repetitions use the same , they pass together exactly when , so the acceptance probability is still , not . The claim fails because the repetitions are perfectly correlated. Repair: draw a fresh random bit for each repetition, three bits in total; the three tests are then independent and all pass with probability .
Practice and solutions
Quick check
(In the padded contradictory formula above, calculate the optimum fraction of satisfied clauses.)
Count how many clauses one assignment can satisfy.
Solution · Answer
Every assignment violates one of the two contradictory clauses and satisfies the other and all tautologies. Thus the optimum is .
Quick check
(Why does the approximation proof evaluate the returned assignment instead of trusting a numerical claim supplied by the approximation algorithm?)
Ask what the soundness statement is about.
Solution · Answer
Soundness of the gap applies to actual assignments. Evaluating the output certifies its true value and ensures it cannot exceed the no-case optimum even if an algorithm's reported number is wrong.
Quick check
(In the numerical gap example, why would an approximation ratio of only not yield the stated threshold argument?)
Compare the guarantee on a yes-output with the best no-output value.
Solution · Answer
On a yes-output the guarantee would be only , which is below the no-case upper bound . The two ranges overlap, so that guarantee alone does not distinguish the cases.
Quick check
(Explain why a PCP proof cannot be altered after the verifier chooses its random query positions.)
Recall what the soundness bound quantifies over.
Solution · Answer
Soundness bounds acceptance of each fixed proof over the verifier's random coins. If the alleged proof could respond adaptively after seeing the queries, the model and its quantifiers would be different, and the stated PCP guarantee would not apply.