P/poly

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

𝐏/𝐩𝐨𝐥𝐲=∪c∈ℕ𝐒𝐈𝐙𝐄(nc).

wobei 𝐒𝐈𝐙𝐄(nc) 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 n eine Hinweiszeichenkette αn, die es bei seiner Berechnung verwenden darf, wenn die Eingabe eine Größe von n hat.

Seien T,a:ℕ→ℕ Funktionen. Die Klasse von Sprachen, die von time-T(n) Turingmaschinen mit Hinweis a(n) entschieden werden können, bezeichnet mit 𝐃𝐓𝐈𝐌𝐄(T(n))/a(n), enthält jede Sprache L, so dass es eine Sequenz {αn}n∈ℕ von Zeichenketten mit αn∈{0,1}a(n) und eine Turingmaschine M gibt, für die für jede Eingabe x∈{0,1}n gilt, dass

M(x,αn)=1⇔x∈L

wobei auf einer Eingabe (x,α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:

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

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

∀xProbR[R∈Bad(x)]≤1en.

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

ProbR[∃xR∈Bad(x)]≤2nen<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