PCP-Theorem

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:

NP = PCP (O(log n), O(1))

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.

• Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy: Proof verification and the hardness of approximation Problems. In: Journal of the ACM. Bd. 45, 1998, S. 501–555 (Beweis des PCP-Theorems)
• Sanjeev Arora, Shmuel Safra: Probabilistic checking of proofs: a new characterization of NP. In: Journal of the ACM. Bd. 45, 1998, S. 70–122 (Beweis des Theorems)
• Sanjeev Arora: How NP got a new definition: a survey of probabilistically checkable proofs, ICM Peking 2002, Arxiv
• Laszlo Babai, Lance Fortnow, Leonid Levin, Carsten Lund: Non deterministic exponential time has two-prover interactive proofs. In: Proc. of the 23. ACM Symposium on the theory of computing. 1991
• Uriel Feige, Shafi Goldwasser, Laszlo Lovasz, Shmuel Safra, Mario Szegedy: Interactive proofs and the hardness of approximating cliques. In: Journal of the ACM. Band 43, 1996, S. 268–292.
• Irit Dinur: The PCP theorem by gap amplification. Technical Report 2005 und Journal of the ACM, Band 54, 2007, S. 1–12, Online
• Jaikumar Radhakrishnan, Madhu Sudan: On Dinur’s Proof of the PCP Theorem. In: Bulletin AMS. Bd. 44, 2007, S. 19–61, Online

• A history of the PCP theorem von Ryan O'Donnell und Venkatesan Guruswami von der University of Washington