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 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. 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).

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. 2005 gelang Irit Dinur ein radikal vereinfachter neuer Beweis des PCP Theorems.

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
• 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
• Jaikumar Radhakrishnan, Madhu Sudan On Dinur´s Proof of the PCP Theorem, Bulletin AMS, Bd.44, 2007, S.19-61

Weblinks

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