In computational complexity theory, the PCP theorem (also known as the PCP characterization theorem) states that every decision problem in the NP complexity class has probabilistically checkable proofs (proofs that can be checked by a randomized algorithm) of constant query complexity and logarithmic randomness complexity (uses a logarithmic number of random bits).

The PCP theorem says that for some universal constant ${\displaystyle K}$, for every ${\displaystyle n}$, any mathematical proof for a statement of length ${\displaystyle n}$ can be rewritten as a different proof of length ${\displaystyle \operatorname {poly} (n)}$ that is formally verifiable with 99% accuracy by a randomized algorithm that inspects only ${\displaystyle K}$ letters of that proof.

The PCP theorem is the cornerstone of the theory of computational hardness of approximation, which investigates the inherent difficulty in designing efficient approximation algorithms for various optimization problems. It has been described by Ingo Wegener as "the most important result in complexity theory since Cook's theorem" and by Oded Goldreich as "a culmination of a sequence of impressive works […] rich in innovative ideas".

The PCP theorem states that $${\displaystyle {\mathsf {NP}}={\mathsf {PCP}}[O(\log n),O(1)]}$$ where ${\displaystyle {\mathsf {NP}}}$ is the complexity class of problems solvable in nondeterministic polynomial time and where ${\displaystyle {\mathsf {PCP}}[r(n),q(n)]}$ is the class of problems for which a probabilistically checkable proof of a solution can be given, such that the proof can be checked in polynomial time using ${\displaystyle r(n)}$ bits of randomness and by reading ${\displaystyle q(n)}$ bits of the proof, correct proofs are always accepted, and incorrect proofs are rejected with probability at least ${\displaystyle {\tfrac {1}{2}}}$. The variable ${\displaystyle n}$ is the length in bits of the description of a problem instance. Note further that the verification algorithm is non-adaptive: the choice of bits of the proof to check depend only on the random bits and the description of the problem instance, not the actual bits of the proof.

An alternative formulation of the PCP theorem states that the maximum fraction of satisfiable constraints of a constraint satisfaction problem is NP-hard to approximate within some constant factor.

Formally, for some constants ${\displaystyle q}$ and ${\displaystyle \alpha <1}$, the following promise problem ${\displaystyle (L_{\mathrm {yes} },L_{\mathrm {no} })}$ is an NP-hard decision problem:

where ${\displaystyle \Phi }$ is a constraint satisfaction problem (CSP) over a Boolean alphabet with at most ${\displaystyle q}$ variables per constraint.

The connection to the class ${\displaystyle {\mathsf {PCP}}}$ mentioned above can be seen by noticing that checking a constant number of bits ${\displaystyle q}$ in a proof can be seen as evaluating a constraint in ${\displaystyle q}$ Boolean variables on those bits of the proof. Since the verification algorithm uses ${\displaystyle O(\log n)}$ bits of randomness, it can be represented as a CSP as described above with ${\displaystyle \operatorname {poly} (n)}$ constraints. The other characterisation of the PCP theorem then guarantees the promise condition with ${\displaystyle \alpha ={\tfrac {1}{2}}}$: if the NP problem's answer is yes, then every constraint (which corresponds to a particular value for the random bits) has a satisfying assignment (an acceptable proof); otherwise, any proof should be rejected with probability at least ${\displaystyle {\tfrac {1}{2}}}$, which means any assignment must satisfy fewer than ${\displaystyle {\tfrac {1}{2}}}$ of the constraints (which means it will be accepted with probability lower than ${\displaystyle {\tfrac {1}{2}}}$). Therefore, an algorithm for the promise problem would be able to solve the underlying NP problem, and hence the promise problem must be NP-hard.