die Theorie der probabilistically checkable proofs (PCP).

Das PCP-Theorem enthält eine neue Charakterisierung von NP.

Ein Verifizierer V ist eine Turing-Maschine. Er kann probabilistisch Beweise für die Sprache L überprüfen, wenn es für jedes x ∈ L einen Beweis, d. h. eine Bitfolge, gibt, den V für jede Folge von Zufallsbits akzeptiert und V für jedes x ∉ L und jeden Beweis nur mit Wahrscheinlichkeit von höchstens 1/2 (bezogen auf die Zufallsbits) akzeptiert. Der Verifizierer ist \begin{eqnarray}(r(n),q(n))\text{-beschr}\ddot{\mathrm u}{\text {nkt}},\end{eqnarray} wenn für Eingaben der Länge n nur O(r(n)) Zufallsbits benutzt und O(q(n)) Beweisbits gelesen werden. Dann ist NP gleich der Klasse aller Sprachen mit (log n, 1)-beschränkten Verifizierern.

Mit dieser Charakterisierung von NP kann für Probleme wie das Cliquenproblem gezeigt werden, daß ein approximativer Algorithmus mit polynomieller Rechenzeit und konstanter Güte (Güte eines Algorithmus) nur existieren kann, wenn NP=P (NP-Vollständigkeit) ist.

Das PCP-Theorem gilt als wichtigstes Theorem der Komplexitätstheorie in der Zeit von 1985 bis 1995.