PCP-Theorem

Das PCP-Theorem ist ein Satz aus der theoretischen Informatik (Komplexitätstheorie).

Es 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, das 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 an, mit der ein 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, Laszlo Babai, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy, Lance Fortnow, Shafi Goldwasser, Uriel Feige, Laszlo Lovasz. 1991 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.

Literatur

• Sanjev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy Proof verification and the hardness of approximation problems, Journal of the ACM, Bd. 45, 1998, Seite 501–555 (Beweis des PCP Theorems)
• Sanjeev Arora, Shmuel Safra Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM, Bd.45, 1998, S.70-122 (Beweis des Theorems)
• Laszlo Babai, Lance Fortnow, Leonid Levin, Carsten Lund: Non deterministic exponential time has two-prover interactive proofs, 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, 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, pdf
• Jaikumar Radhakrishnan, Madhu Sudan On Dinur´s Proof of the PCP Theorem, Bulletin AMS, Bd.44, 2007, S.19-61, Online

Weblinks

• Ryan O´Donnel, Venkatesan Guruswami History of the PCP Theorem, pdf Datei