Das PCP-Theorem ist ein Satz aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik.
Das PCP-Theorem beruht auf dem Konzept des zufällig verifizierbaren Beweises eines mathematischen Satzes (probabilistic checkable proof, PCP), der wiederum auf das Konzept Interaktiver Beweissysteme zurückgeht, die Anfang der 1980er Jahre von Shafi Goldwasser, Charles Rackoff und Silvio Micali eingeführt wurden. Dahinter steckte die Idee, dass die Verifizierung von Beweisen mathematischer Sätze meist sehr viel einfacher ist als der Beweis selbst (was bei den Autoren einen kryptographischen Hintergrund hatte).
Ein Beweis einer Behauptung A besteht aus einer Folge von Ableitungsregeln angewandt auf die Axiome des formalen Systems. Das wird in Form eines Algorithmus, Verifizierer genannt, formalisiert, der eine Behauptung A und die „Evidenz“ E als Input hat und berechnet, ob E ein Beweis von A ist. PCP geht davon aus, dass zur Verifizierung eines Beweises ein Zufallszahlengenerator zur Verfügung steht und ein direkter Zugang (Orakel) auf beliebige Bits an beliebigen Stellen des Beweises. In das PCP geht dann noch die Mindestwahrscheinlichkeit ein, mit der ein korrekter Beweis akzeptiert wird (sie sollte bei 1 liegen, Completeness) und die Mindestwahrscheinlichkeit, mit der ein falscher Beweis zurückgewiesen wird (sollte bei 1/2 liegen, Soundness). Das PCP-Theorem macht dann quantitative Aussagen über die Größe der verwendeten Bestandteile des Verifizierungsalgorithmus in Abhängigkeit von der Größe des Beweises (Länge n Bits): die Zahl der zu erfragenden Bits ist unabhängig von n durch eine universelle Konstante K begrenzt und die Zahl der verwendeten Bits des Zufallszahlengenerators ist von der Größenordnung log (n).
PCP-Theorem: Jedes Entscheidungsproblem in der NP-Klasse kann durch einen PCP-Beweis mit konstanter Komplexität der Fragen und logarithmischer Zufallskomplexität gelöst werden:
Das Theorem basiert auf einer langen Reihe von Arbeiten, in denen das PCP-Konzept entwickelt wurde. Beteiligt waren in den 1990er Jahren Sanjeev Arora, Shmuel Safra, László Babai, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy, Lance Fortnow, Shafi Goldwasser, Uriel Feige und László Lovász. 2001 erhielten Arora, Goldwasser, Feige, Lund, Motwani, Safra, Lovasz, Sudan und Szegedy für den Beweis den Gödel-Preis. Feige und Ko-Autoren stellten 1996 eine Äquivalenz des Theorems zur Nicht-Approximierbarkeit bestimmter Optimierungsprobleme her. Der Beweis wurde dann von Arora, Safra und anderen 1998 veröffentlicht.
2005 gelang Irit Dinur ein radikal vereinfachter neuer Beweis des PCP-Theorems. Dinur ging ebenfalls von der Lösung eines Optimierungsproblems (Constraint Satisfaction) aus, um das äquivalente PCP Problem zu beweisen.