P/poly

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

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

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

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

$\mathbf {P_{/poly}} =\cup _{c\in \mathbb {N} }\mathbf {SIZE} (n^{c}).$

wobei $\mathbf {SIZE} (n^{c})$ die Menge der Entscheidungsprobleme bezeichnet, die von Schaltkreisen polynomieller Größe entschieden werden können.

Alternativ kann $\mathbf {P_{/poly}}$ durch Turingmaschinen mit Hinweisfunktion definieren. Eine solche Maschine hat für jede Eingabe der Länge $n$ eine Hinweiszeichenkette $\alpha _{n}$, die es bei seiner Berechnung verwenden darf, wenn die Eingabe eine Größe von $n$ hat.

Seien $T,a:\mathbb {N} \rightarrow \mathbb {N}$ Funktionen. Die Klasse von Sprachen, die von time-T(n) Turingmaschinen mit Hinweis $a(n)$ entschieden werden können, bezeichnet mit $\mathbf {DTIME} (T(n))/a(n)$, enthält jede Sprache L, so dass es eine Sequenz $\{\alpha _{n}\}_{n\in \mathbb {N} }$ von Zeichenketten mit $\alpha _{n}\in \{0,1\}^{a(n)}$ und eine Turingmaschine M gibt, für die für jede Eingabe $x\in \{0,1\}^{n}$ gilt, dass

$M(x,\alpha _{n})=1\Leftrightarrow x\in L$

wobei auf einer Eingabe $(x,\alpha _{n})$ die Maschine M höchstens $O(T(n))$ Schritte benötigt.

Bedeutung von P/poly

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, $\Sigma _{2}^{\mathsf {P}}$. Dies ergibt sich aus dem Satz von Karp-Lipton. Außerdem impliziert NP ⊆ P/poly, dass AM = MA.
• Falls PSPACE ⊆ P/poly, dann gilt $\mathbf {PSPACE} =\mathbf {\Sigma _{2}^{P}} \cap \mathbf {\Pi _{2}^{P}}$ 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. 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 ${\mathsf {EXPTIME}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}$ (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.
• Falls EXP^NP ⊆ P/poly, dann gilt, dass ${\mathsf {EXP^{NP}}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}$. (Buhrman, Homer)
• Es ist bekannt, dass MA_EXP, die exponentielle Version von MA, nicht in P/poly enthalten ist.

Beweis: Falls MA_EXP ⊆ P/poly, dann gilt PSPACE = MA (vgl. oben). Mittels Paddingtechnik folgt, EXPSPACE = MA_EXP 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, NP^A keine Teilmenge von P^A/poly mit Wahrscheinlichkeit 1, ist.

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.

BPP ist in P/poly enthalten

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; und das Ergebnis wurde anschließend generalisiert zu BPP ⊆ P/poly von Bennett und Gill. Varianten des Satzes zeigen, dass BPL in L/poly und AM in NP/poly enthalten sind.

Beweis

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/eⁿ 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:

$\forall x\,{\mbox{Prob}}_{R}[R\in {\mbox{Bad}}(x)]\leq {\frac {1}{e^{n}}}.$

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

${\mbox{Prob}}_{R}[\exists x\,R\in {\mbox{Bad}}(x)]\leq {\frac {2^{n}}{e^{n}}}<1.$

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.

Siehe auch

• Liste von Komplexitätsklassen
• Komplexitätstheorie