The PCP Theorem, in depth: probabilistically checkable proofs, the gap-3SAT form, a runnable linearity test, how the proof works and the hardness-of-approximation map

Verifiers, randomness and queries

A verifier V is a polynomial-time algorithm with access to the input x, a string of random bits, and a proof string pi that it can read one position at a time. The class PCP[r(n), q(n)] contains languages L with a verifier that uses at most r(n) random bits and reads at most q(n) positions of pi, such that:

• Completeness: if x is in L, some proof pi makes V accept with probability 1.
• Soundness: if x is not in L, for every proof pi, V accepts with probability at most 1/2.

Ordinary NP verification is PCP[0, poly(n)]: no randomness, read the whole certificate. With O(log n) random bits there are only polynomially many random strings, so a verifier can only ever look at polynomially many proof positions in total, which is why the proof stays polynomially long. The PCP theorem states NP = PCP[O(log n), O(1)]. The containment from right to left is easy: enumerate all random strings and check whether some proof makes all of them accept, which is an NP question. The surprise is the other direction. Repeating the verifier k times drives the soundness error down to 2^-k, still with constant queries. Håstad later showed that three queries suffice, with soundness just above 1/2 at the cost of completeness 1 - epsilon rather than exactly 1.

Verifiers, randomness and queries

A verifier V is a polynomial-time algorithm with access to the input x, a string of random bits, and a proof string pi that it can read one position at a time. The class PCP[r(n), q(n)] contains languages L with a verifier that uses at most r(n) random bits and reads at most q(n) positions of pi, such that:

• Completeness: if x is in L, some proof pi makes V accept with probability 1.
• Soundness: if x is not in L, for every proof pi, V accepts with probability at most 1/2.

Ordinary NP verification is PCP[0, poly(n)]: no randomness, read the whole certificate. With O(log n) random bits there are only polynomially many random strings, so a verifier can only ever look at polynomially many proof positions in total, which is why the proof stays polynomially long. The PCP theorem states NP = PCP[O(log n), O(1)]. The containment from right to left is easy: enumerate all random strings and check whether some proof makes all of them accept, which is an NP question. The surprise is the other direction. Repeating the verifier k times drives the soundness error down to 2^-k, still with constant queries. Håstad later showed that three queries suffice, with soundness just above 1/2 at the cost of completeness 1 - epsilon rather than exactly 1.

The gap form and why it is equivalent

Algorithm designers rarely use the verifier form. The equivalent statement is about a gap: there is a constant rho below 1 and a polynomial-time reduction from 3SAT that maps satisfiable formulas to satisfiable formulas, and unsatisfiable formulas to formulas in which every assignment leaves at least a (1 - rho) fraction of clauses unsatisfied. Distinguishing the two cases, called gap-3SAT, is NP-hard.

Why the two are the same. From gap to PCP: to check x, reduce it to the gap formula; the proof is an assignment; the verifier picks a random clause, using O(log m) bits, reads its three variables and checks it. If x is in L all clauses pass; otherwise at least a constant fraction fail, and a constant number of repetitions brings the acceptance probability below one half. From PCP to gap: for each of the polynomially many random strings, the verifier's decision depends on a constant number of proof bits, so write that decision as a constant-size 3CNF over proof-bit variables. The conjunction of all of these is satisfiable if x is in L. If x is not in L, at least half of the random strings reject under any proof, and each contributes at least one false clause out of a constant number, so a constant fraction of all clauses must fail.

The gap form is what makes approximation hard. An algorithm with ratio better than rho for MAX-3SAT would separate the two cases, and so decide 3SAT. Classic reductions such as those in textbook 3SAT reductions preserve membership but not gaps; hardness of approximation needs gap-preserving reductions starting from a PCP.

A local test you can run

The building block inside every algebraic PCP proof is a local test: a check that reads a few positions and rejects, with probability related to the distance, any table that is far from having the right structure. The Blum-Luby-Rubinfeld linearity test is the simplest. A function f from n-bit strings to one bit is linear if f(x xor y) = f(x) xor f(y) for all x and y, which means it is a parity of some fixed subset of bits. The test reads three entries of the truth table:

import random
n, N = 10, 1 << 10
rng = random.Random(1)

def blr_reject_rate(table, trials=20000):
    rej = 0
    for _ in range(trials):
        x, y = rng.randrange(N), rng.randrange(N)
        if table[x] ^ table[y] != table[x ^ y]:
            rej += 1
    return rej / trials

parity = lambda x: bin(x).count("1") & 1
a = 0b1011001101
linear = [parity(a & x) for x in range(N)]          # a true linear function
for frac in (0.01, 0.05, 0.10, 0.20):
    t = linear[:]
    for x in rng.sample(range(N), int(frac * N)):   # corrupt a fraction of entries
        t[x] ^= 1
    print(frac, round(blr_reject_rate(t), 3))

The linear table was never rejected. Corrupting 1, 5, 10 and 20 percent of entries gave measured rejection rates of 0.030, 0.132, 0.247 and 0.391, and a uniformly random table is rejected about half the time. The theorem behind the test guarantees a rejection probability of at least delta, the fraction of entries that must change to reach the nearest linear function; for small delta it is close to 3 delta, as the numbers show, because each of the three queried positions is a chance to hit a corrupted entry.

The same arithmetic tells you how many local checks a gap needs. If at least a fraction epsilon of checks fail, k independent checks all pass with probability (1 - epsilon)^k. To catch a cheat with probability 0.99 you need k = 7 checks at epsilon = 0.5, 44 at 0.1, 459 at 0.01 and 4,603 at 0.001. A bigger gap is what makes a constant number of queries enough, and making the gap a constant is the hard part of the theorem.

How the theorem is proved

The original proof encodes an NP witness with error-correcting codes built from low-degree polynomials over finite fields, so that a corrupted or inconsistent proof is far from every valid codeword and local tests like the one above notice. Two verifiers are built: one with O(log n) randomness and polylogarithmic queries, using the low-degree test and the sum-check idea from interactive proofs, and one with polynomial randomness but constant queries, using the Hadamard code, which is exactly the table of all parities and is tested by BLR. Proof composition then lets the outer verifier delegate its query check to the inner one, cutting queries to a constant while keeping randomness logarithmic.

In 2007 Irit Dinur gave a combinatorial proof. Start from a constraint graph whose unsatisfiable instances have a tiny gap, about 1/m. Each round preprocesses the graph into a constant-degree expander, then powers it so each new constraint looks at a neighbourhood of constant radius, which roughly doubles the gap at the cost of a larger alphabet, then composes with a constant-size PCP to bring the alphabet back down. Each round grows the instance by a constant factor and doubles the gap, so O(log m) rounds reach a constant gap with polynomial total size.

The idea of a proof checked by sampling also drives practical cryptography: Kilian and Micali turned PCPs into succinct arguments, and modern STARK-style proof systems use interactive oracle proofs, a descendant of PCPs, to verify large computations by reading a few committed positions. The related idea of convincing a verifier without revealing a witness is covered in zero-knowledge proofs.

The hardness-of-approximation map

Gap-preserving reductions from PCPs, often with stronger PCPs built for one problem, give tight or near-tight thresholds. The hypothesis matters; results under the Unique Games Conjecture (UGC) are conditional on a statement that remains open.

Read each row as a budget. For set cover, the greedy algorithm in greedy set cover is essentially the best possible in the worst case, so spend effort on instance structure or exact solvers, not on a better general ratio. For vertex cover, the simple 2-approximation in vertex cover approximation may be optimal, and anyone claiming 1.9 in polynomial time on all graphs is claiming to refute UGC.

Worked example: MAX-3SAT and the 7/8 line

Take MAX-3SAT where every clause has three distinct variables. A uniformly random assignment falsifies a clause only when all three literals are false, with probability 1/8, so it satisfies 7/8 of the clauses in expectation. The method of conditional expectations turns that into a deterministic algorithm: fix variables one at a time, each time choosing the value that keeps the expected number of satisfied clauses, over random choices for the rest, at least as high.

def expected_sat(clauses, assign):
    total = 0.0
    for cl in clauses:                      # cl: tuple of DIMACS literals, e.g. (1, -4, 7)
        p_unsat = 1.0
        for lit in cl:
            v = abs(lit)
            if v in assign:
                if assign[v] == (lit > 0):
                    p_unsat = 0.0
                    break
            else:
                p_unsat *= 0.5
        total += 1 - p_unsat
    return total

def derandomised(clauses, nvars):
    assign = {}
    for v in range(1, nvars + 1):
        assign[v] = True
        t = expected_sat(clauses, assign)
        assign[v] = False
        f = expected_sat(clauses, assign)
        assign[v] = t >= f
    return assign

The expectation never drops, starts at 7m/8 and ends at the exact number of satisfied clauses, so the result satisfies at least 7/8 of them. On 300 random formulas of 40 variables and 400 clauses it never fell below the 7/8 line. Håstad's theorem says that for any epsilon greater than 0, no polynomial-time algorithm can guarantee 7/8 + epsilon unless P = NP. So this short loop is optimal in the worst case. That does not stop a SAT solver from satisfying every clause of the instances you actually have; see SAT solving.

What it means when you build systems

• Know the threshold before optimising the ratio. If your problem reduces from one in the table, a worst-case guarantee better than its threshold is out of reach. Spend effort on exact methods for your sizes, on heuristics, or on structure.
• Worst case is not your case. Hardness is about all instances. Real inputs often have small treewidth, planarity, bounded degree or metric costs, and many problems that are hard to approximate in general have approximation schemes on such classes; see PTAS and FPTAS.
• Use the ratio as a quality bar. If a heuristic beats the guaranteed algorithm by a wide margin on your data, that is useful information; if it is worse, ship the guaranteed one.
• Report bounds. LP relaxations and duals give lower bounds on the optimum, so you can say a solution is within 3 percent of optimal on this instance even when no algorithm can promise that in general.
• Gap thinking for verification. When auditing a large computation by sampling, the number of samples depends on the fraction of failures you must catch, exactly as in the gap calculation above.

Common misreadings

• It does not say problems are hard to solve in practice. It concerns worst-case polynomial-time guarantees under P ≠ NP.
• A constant number of queries does not mean a constant-size proof. The PCP proof is polynomially long and generally much longer than the ordinary witness.
• Not every result in the table needs only P ≠ NP. Check the hypothesis column before quoting a bound; UGC results are conditional.
• Approximation hardness is not inherited by reductions automatically. Ordinary Karp reductions, described in NP-completeness, preserve yes and no answers but can destroy gaps.
• Soundness of one half is not a weakness. Repetition reduces it exponentially at constant cost per round.

What to do next

1. Run the BLR test and confirm that the rejection rate grows with the corruption fraction.
2. Run the derandomised MAX-3SAT loop on your own formulas and compare it to a SAT solver.
3. For each NP-hard problem in your system, find its row in a hardness table and write down the best guarantee you can hope for and under which hypothesis.
4. Add lower bounds from an LP relaxation to your solver logs so you can report instance-level gaps.
5. Check whether your inputs have structure, such as bounded treewidth, planarity or metric costs, that admits better algorithms than the worst case allows.