P/poly

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
QS-Informatik
Beteilige dich an der Diskussion!
Dieser Artikel wurde wegen inhaltlicher Mängel auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen, und beteilige dich an der Diskussion! (+)


Begründung: Es bedarf einer allgemeinverständlichen Einleitung, die zumindest darstellt, worum es geht

In der Komplexitätstheorie ist P/poly die Komplexitätsklasse von Sprachen die von polynomzeit-beschränkten Turing-Maschinen mit polynomiell beschränkter Hinweisfunktion erkannt werden. Sie wird auch äquivalent als die Klasse PSIZE von Sprachen definiert, die Schaltkreise polynomieller Größe besitzen.[1][2] Dies bedeutet, dass eine Maschine, die eine P/poly Sprache erkennt, je nach Länge der Eingabe eine andere Hinweisfunktion oder eine andere Schaltung verwenden kann und dass die Hinweisfunktion oder Schaltung nur von der Größe der Eingabe abhängt.

Zum Beispiel kann der beliebte Miller-Rabin-Test als P/poly-Algorithmus formuliert werden: Der „Rat“ ist eine Liste von Kandidaten a, die zu testen sind. Es ist möglich, eine Liste mit höchstens n Werten so vorab zu berechnen, dass jede zusammengesetzte n-Bit-Nummer mit Sicherheit einen Zeugen a in der Liste besitzt. Um beispielsweise die Primalität von 32-Bit-Zahlen korrekt zu bestimmen, reicht es aus, a = 2, 7 und 61 zu testen.[3] Die Existenz von kurzen Listen von Zeugen für Kandidaten folgt aus der Tatsache, dass für jedes zusammengesetzte n 3/4 aller möglichen a-Werte Zeugen sind. Ein einfaches Zählargument ähnlich dem im Beweis unten, dass BPP in P/poly ist, zeigt, dass es für jede Eingabegröße eine geeignete Liste von a-Werten existiert, obwohl es aufwändig sein kann, sie zu finden.

P/poly wird im Gegensatz zu anderen Polynomzeitklassen wie P oder BPP im Allgemeinen nicht als praktische Klasse für Berechnungen angesehen. In der Tat enthält sie jede unentscheidbare unäre Sprache, von der keine im Allgemeinen von realen Computern gelöst werden kann. Wenn andererseits die Eingabelänge durch eine relativ kleine Zahl begrenzt ist und die Hinweiszeichenfolgen kurz sind, können praktische Algorithmen mit einer separaten teuren Vorverarbeitungsphase und einer schnellen Verarbeitungsphase wie im obigen Beispiel modelliert werden.

Formale Definition

[Bearbeiten | Quelltext bearbeiten]

Die Komplexitätsklasse P/poly kann in Bezug auf SIZE wie folgt definiert werden:

wobei die Menge der Entscheidungsprobleme bezeichnet, die von Schaltkreisen polynomieller Größe entschieden werden können.

Alternativ kann durch Turingmaschinen mit Hinweisfunktion definieren. Eine solche Maschine hat für jede Eingabe der Länge eine Hinweiszeichenkette , die es bei seiner Berechnung verwenden darf, wenn die Eingabe eine Größe von hat.

Seien Funktionen. Die Klasse von Sprachen, die von time-T(n) Turingmaschinen mit Hinweis entschieden werden können, bezeichnet mit , enthält jede Sprache L, so dass es eine Sequenz von Zeichenketten mit und eine Turingmaschine M gibt, für die für jede Eingabe gilt, dass

wobei auf einer Eingabe die Maschine M höchstens Schritte benötigt.[4]

Bedeutung von P/poly

[Bearbeiten | Quelltext bearbeiten]

P/poly ist aus mehreren Gründen eine wichtige Komplexitätsklasse. Für die theoretische Informatik gibt es mehrere wichtige Eigenschaften, die von P/poly abhängen:

  • Falls NP ⊆ P/poly, dann kollabiert PH (die Polynomialzeithierarchie) auf die zweite Stufe, . Dies ergibt sich aus dem Satz von Karp-Lipton. Außerdem impliziert NP ⊆ P/poly, dass AM = MA.[5]
  • Falls PSPACE ⊆ P/poly, dann gilt und sogar PSPACE = MA.
Beweis: Man betrachte eine Sprache L aus PSPACE. Es ist bekannt, dass es ein interaktives Beweissystem für L existiert, bei dem Aktionen des Prüfenden von einer PSPACE-Maschine ausgeführt werden können. Unter der Annahme kann der Prüfer durch einen Schaltkreis polynomieller Größe ersetzt werden. Daher hat L ein MA-Protokoll: Merlin sendet den Schaltkreis als Beweis, und Arthur kann das IP-Protokoll ohne zusätzliche Hilfe selbst simulieren.
  • Falls P#P ⊆ P/poly, dann gilt P#P = MA.[6] Der Beweis ist ähnlich wie oben, basierend auf einem interaktiven Protokoll für die Permanente und der #P-Vollständigkeit selbiger.
  • Falls EXPTIME ⊆ P/poly, dann gilt (Satz von Bonnet-Myers) und sogar EXPTIME = MA.
  • Falls NEXPTIME ⊆ P/poly, dann gilt NEXPTIME = EXPTIME und sogar NEXPTIME = MA. Umgekehrt impliziert NEXPTIME = MA, dass NEXPTIME ⊆ P/poly.[7]
  • Falls EXPNP ⊆ P/poly, dann gilt, dass . (Buhrman, Homer)[8][9]
  • Es ist bekannt, dass MAEXP, die exponentielle Version von MA, nicht in P/poly enthalten ist.
Beweis: Falls MAEXP ⊆ P/poly, dann gilt PSPACE = MA (vgl. oben). Mittels Paddingtechnik folgt, EXPSPACE = MAEXP und daher EXPSPACE ⊆ P/poly, was allerdings durch Diagonalisierung widerlegt werden kann.

Einer der interessantesten Gründe, warum P/poly wichtig ist, ist die Eigenschaft, dass wenn NP keine Teilmenge von P/poly ist, dann P ≠ NP gilt. Diese Beobachtung stand im Zentrum vieler Beweisversuche zu P ≠ NP. Es ist bekannt, dass für ein zufälliges Orakel A, NPA keine Teilmenge von PA/poly mit Wahrscheinlichkeit 1, ist.[1]

P/poly wird auch im Bereich der Kryptographie verwendet. Sicherheit wird oft „gegen“ P/poly-Gegner definiert. Dies schließt nicht nur die meisten praktischen Berechnungsmodelle wie BPP ein, sondern lässt auch die Möglichkeit zu, dass Gegner umfangreiche Vorberechnungen für Eingaben bis zu einer bestimmten Länge durchführen können, wie z. B. bei der Konstruktion von Regenbogentabellen.

Obwohl nicht alle Sprachen in P/poly spärliche Sprachen sind, gibt es eine polynomzeit-beschränkte Turing-Reduktion von jeder Sprache in P/poly auf eine spärliche Sprache.[10]

BPP ist in P/poly enthalten

[Bearbeiten | Quelltext bearbeiten]

Adlemans Satz besagt, dass BPP ⊆ P/poly. Dabei ist BPP die Menge von Problemen, die mit randomisierten Algorithmen mit zweiseitigem Fehler in Polynomzeit lösbar sind. Ein schwächeres Ergebnis wurde zunächst von Leonard Adleman nachgewiesen, nämlich, dass RP ⊆ P/poly;[11] und das Ergebnis wurde anschließend generalisiert zu BPP ⊆ P/poly von Bennett und Gill.[12] Varianten des Satzes zeigen, dass BPL in L/poly und AM in NP/poly enthalten sind.

Sei L eine Sprache in BPP und sei M(x,r) ein polynomzeit-beschränkter Algorithmus, der L mit einem Fehler ≤ 1/3 entscheidet (wobei x die Eingabezeichenkette und r eine Menge zufälliger Bits ist).

Konstruiere eine neue Maschine M'(x,R), die in M 18n Schritten läuft und einen Mehrheitsentscheid der Ergebnisse (wobei n die Eingabelänge und R eine Folge von 18n unabhängig zufälligen rs ist) nimmt. Daher gilt, M' ist ebenso polynomzeit-beschränkt und hat eine Fehlerwahrscheinlichkeit ≤ 1/en beschränkt durch die Chernoff-Ungleichung (vgl. BPP). Wenn wir R entsprechend anpassen können, erhalten wir einen deterministischen Algorithmus.

Falls Bad(x) definiert ist als {R: M'(x,R) ist inkorrekt}, dann ist:

Die Eingabegröße ist n, es gibt also 2n mögliche Eingaben. Somit ist durch die Bonferroni-Ungleichung die Wahrscheinlichkeit, dass ein zufälliges R für mindestens eine Eingabe x schlecht ist

Mit anderen Worten, die Wahrscheinlichkeit, dass R für einige x schlecht ist, ist kleiner als 1, daher muss ein R existieren, welches für alle x gut ist. Man nehme ein solches R als Hinweiszeichenfolge in dem beschriebenen P/poly-Algorithmus.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. a b Jack H. Lutz, William J. Schmidt: Circuit size relative to pseudorandom oracles. In: Theoretical Computer Science. Band 1, Nr. 107, 1993, S. 95–119, doi:10.1016/0304-3975(93)90256-S.
  2. Peter Bro Miltersen: Lecture notes on computational complexity. Archiviert vom Original (nicht mehr online verfügbar) am 23. Februar 2012; abgerufen am 25. Dezember 2009.
  3. Finding primes & proving primality
  4. Sanjeev Arora, Boaz Barak: Computational complexity. A modern approach. Hrsg.: Cambridge University Press. 2009, ISBN 978-0-521-42426-4.
  5. Vikraman Arvind, Johannes Köbler, Uwe Schöning, Rainer Schuler: If NP has polynomial-size circuits, then MA = AM. In: Theoretical Computer Science. Band 2, Nr. 137, 1995, S. 279–282, doi:10.1016/0304-3975(95)91133-B (hu-berlin.de).
  6. László Babai, Lance Fortnow, Carsten Lund: Nondeterministic exponential time has two-prover interactive protocols. In: Computational Complexity. Band 1, Nr. 1, 1991, S. 3–40, doi:10.1007/BF01200056.
  7. Russell Impagliazzo, Valentine Kabanets, Avi Wigderson: In search of an easy witness: exponential time vs. probabilistic polynomial time. In: Journal of Computer and System Sciences. Band 4, Nr. 65, 2002, S. 672–694, doi:10.1016/S0022-0000(02)00024-7 (ias.edu [PDF]).
  8. Harry Buhrman, Steven Homer.: Superpolynomial circuits, almost sparse oracles and the exponential hierarchy. In: Proceedings of the 12th Conference on Foundations of Software Technology and Theoretical Computer Science. Springer-Verlag, London, UK 1992, S. 116–127.
  9. A Note on the Karp-Lipton Collapse for the Exponential Hierarchy
  10. Jin-Yi Cai. Lecture 11: P/poly, Sparse Sets, and Mahaney's Theorem. CS 810: Introduction to Complexity Theory. The University of Wisconsin–Madison. September 18, 2003.
  11. Leonard Adleman: Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computer Science. Symposium on Foundations of Computer Science. In: Two theorems on random polynomial time. 1978, S. 75–83, doi:10.1109/SFCS.1978.37.
  12. Charles H. Bennett, John Gill. Relative to a Random Oracle A, PA ≠ NPA ≠ co-NPA with probability 1. [1]