imported>Sokrates 399: Typografie (Apostroph ≠ Accent aigu ≠ Prime)

2026-04-21T06:57:21Z

Typografie (Apostroph ≠ Accent aigu ≠ Prime)

Neue Seite

Das '''PCP-Theorem''' ist ein Satz aus der [[Komplexitätstheorie]], einem Teilgebiet der [[Theoretische Informatik|Theoretischen Informatik]].

== Aussage ==

Das PCP-Theorem beruht auf dem Konzept des zufällig verifizierbaren Beweises eines mathematischen Satzes (probabilistic checkable proof, PCP), der wiederum auf das Konzept [[Interaktives Beweissystem|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 [[Kryptographie|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 [[Bit]]s 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 (Komplexitätsklasse)|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))

== Geschichte ==
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.

== Literatur ==
* 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, [https://arxiv.org/abs/cs/0304038 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, [https://eccc.weizmann.ac.il//report/2005/046/ Online]
* Jaikumar Radhakrishnan, Madhu Sudan: ''On Dinur’s Proof of the PCP Theorem.'' In: ''Bulletin AMS.'' Bd. 44, 2007, S. 19–61, [https://www.ams.org/journals/bull/2007-44-01/S0273-0979-06-01143-8/ Online]

== Weblinks ==
* [https://courses.cs.washington.edu/courses/cse533/05au/pcp-history.pdf A history of the PCP theorem] von Ryan O'Donnell und Venkatesan Guruswami von der [[University of Washington]]

[[Kategorie:Komplexitätstheorie]]

PCP-Theorem - Versionsgeschichte

imported>Sokrates 399: Typografie (Apostroph ≠ Accent aigu ≠ Prime)