www.wikidata.de-de.nina.az

PCP Theorem Das ist ein Satz aus der Komplexitätstheorie einem Teilgebiet der Theoretischen Informatik Inhaltsverzeichni

PCP-Theorem

Das PCP-Theorem ist ein Satz aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik.

Aussage Bearbeiten

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:

Geschichte Bearbeiten

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 Bearbeiten

  • 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

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Das PCP Theorem ist ein Satz aus der Komplexitatstheorie einem Teilgebiet der Theoretischen Informatik Inhaltsverzeichnis 1 Aussage 2 Geschichte 3 Literatur 4 WeblinksAussage BearbeitenDas PCP Theorem beruht auf dem Konzept des zufallig verifizierbaren Beweises eines mathematischen Satzes probabilistic checkable proof PCP der wiederum auf das Konzept Interaktiver Beweissysteme zuruckgeht die Anfang der 1980er Jahre von Shafi Goldwasser Charles Rackoff und Silvio Micali eingefuhrt wurden Dahinter steckte die Idee dass die Verifizierung von Beweisen mathematischer Satze 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 Verfugung 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 zuruckgewiesen wird sollte bei 1 2 liegen Soundness Das PCP Theorem macht dann quantitative Aussagen uber die Grosse der verwendeten Bestandteile des Verifizierungsalgorithmus in Abhangigkeit von der Grosse des Beweises Lange n Bits die Zahl der zu erfragenden Bits ist unabhangig von n durch eine universelle Konstante K begrenzt und die Zahl der verwendeten Bits des Zufallszahlengenerators ist von der Grossenordnung log n PCP Theorem Jedes Entscheidungsproblem in der NP Klasse kann durch einen PCP Beweis mit konstanter Komplexitat der Fragen und logarithmischer Zufallskomplexitat gelost werden NP PCP O log n O 1 Geschichte BearbeitenDas 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 und Laszlo Lovasz 2001 erhielten Arora Goldwasser Feige Lund Motwani Safra Lovasz Sudan und Szegedy fur den Beweis den Godel Preis Feige und Ko Autoren stellten 1996 eine Aquivalenz des Theorems zur Nicht Approximierbarkeit bestimmter Optimierungsprobleme her Der Beweis wurde dann von Arora Safra und anderen 1998 veroffentlicht 2005 gelang Irit Dinur ein radikal vereinfachter neuer Beweis des PCP Theorems Dinur ging ebenfalls von der Losung eines Optimierungsproblems Constraint Satisfaction aus um das aquivalente PCP Problem zu beweisen Literatur BearbeitenSanjeev 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 OnlineWeblinks BearbeitenA history of the PCP theorem von Ryan O Donnell und Venkatesan Guruswami von der University of Washington Abgerufen von https de wikipedia org w index php title PCP Theorem amp oldid 238280886