P/poly

Im Computerkomplexitätstheorie, P/poly ist ein Komplexitätsklasse Probleme darstellen, die durch kleine Schaltungen gelöst werden können. Genauer gesagt ist es der Satz von formelle Sprachen die polynomiale Kreisfamilien haben. Es kann auch in Bezug auf gleich definiert werden Turing -Maschinen mit Rat, zusätzliche Informationen, die der Turing -Maschine zusammen mit der Eingabe geliefert wurden, die von der Eingangslänge abhängen kann, jedoch nicht von der Eingabe selbst. In dieser Formulierung, P/poly ist die Klasse von Entscheidungsprobleme das kann durch eine Polynomzeit gelöst werden Turing Maschine mit Ratschlägen mit Längenpolynom in der Eingangsgröße.^[1][2] Diese beiden verschiedenen Definitionen machen P/poly zentral zu Komplexität der Schaltung und ungleichmäßige Komplexität.

Zum Beispiel das Populär Miller -Rabin -Primalitätstest kann als formuliert werden P/poly Algorithmus: Der "Rat" ist eine Liste von Kandidaten a Werte zu testen. Es ist möglich, eine Liste von höchstens vorzubereiten n Werte so, dass jeder Komposit n-bitnummer wird mit Sicherheit einen Zeugen haben a In der Liste. Um beispielsweise die Primalität von 32-Bit-Zahlen korrekt zu bestimmen, reicht es aus, zu testen a = 2, 7 und 61.^[3] Die Existenz von kurzen Listen von Zeugen von Kandidaten ergibt sich aus der Tatsache, dass für jedes Komposit n, 3/4s von allen möglich a Werte sind Zeugen; Ein einfaches Zählargument, das dem im Beweis ähnlich ist, das BPP in P/poly Unten zeigt das dort existiert eine geeignete Liste von a Werte für jede Eingangsgröße, obwohl es teuer ist, sie zu finden.

P/polyim Gegensatz zu anderen Polynom-Zeitklassen wie z. P oder BPP, wird im Allgemeinen nicht als praktische Klasse für das Computer angesehen. In der Tat enthält es jeden unentscheidbar Unary Sprache, keines davon kann allgemein durch echte Computer gelöst werden. Wenn die Eingangslänge dagegen durch eine relativ kleine Anzahl begrenzt ist und die Ratschläge kurz sind, kann sie verwendet werden, um praktische Algorithmen mit einer separaten teuren Vorverarbeitungsphase und einer schnellen Verarbeitungsphase wie im obigen Beispiel zu modellieren.

Formale Definition

Das Komplexitätsklasse P/poly kann in Bezug auf definiert werden GRÖSSE folgendermaßen:

$oder$

wo ${\ displayStyle {\ mathsf {size}} (n^{c})}$ ist der Satz von Entscheidungsprobleme Das kann durch polynomarme Leiterfamilien gelöst werden.

Alternative, ${\ displayStyle {\ mathsf {p/poly}}}$ kann mit Verwendung definiert werden Turing -Maschinen Dieser "Rat übernehmen". Eine solche Maschine hat für jeden n, ein Beratungszeichenfolge ${\ displaystyle \ alpha _ {n}}$, was es in seiner Berechnung verwenden darf, wenn die Eingabe die Größe hat n.

Lassen ${\ displayStyle t, a: \ mathbb {n} \ rightarrow \ mathbb {n}}$ Funktionen sein. Die Klasse der Sprachen, die von Time-T (n) entnommen werden können Turing -Maschinen mit ${\ displayStyle a (n)}$ Rat, bezeichnet ${\ displayStyle {\ mathsf {dtime}} (t (n))/a (n)}$, enthält jede Sprache L so dass es eine Sequenz gibt ${\ displaystyle \ {\ alpha _ {n} \} _ {n \ in \ mathbb {n}}}$ von Saiten mit ${\ displaystyle \ alpha _ {n} \ in \ {0,1 \}^{a (n)}}$ und ein tm M befriedigend

${\ displayStyle m (x, \ alpha _ {n}) = 1 \ leftrightarrow x \ in l}$

für jeden ${\ displaystyle x \ in \ {0,1 \}^{n}}$, wo bei der Eingabe ${\ displayStyle (x, \ alpha _ {n})}$ Die Maschine M läuft für höchstens ${\ displayStyle o (t (n))}$ Schritte.^[4]

Bedeutung von P/Poly

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

• Wenn Np ⊆ P/poly dann PH (das Polynomhierarchie) bricht zu ${\ displaystyle \ sigma _ {2}^{\ mathsf {p}}}$. Dieses Ergebnis ist das Karp -Lipton -Theorem; weiter, Np ⊆ P/poly impliziert BIN = Ma ^[5]
• Wenn PSPACE ⊆ P/poly dann $oder$, eben PSPACE = Ma.

Beweis: Betrachten Sie eine Sprache L aus PSPACE. Es ist bekannt, dass es eine gibt Interaktives Proof -System zum L, wo Handlungen des Provers von a durchgeführt werden können PSPACE Maschine. Nach Annahme kann der Prover durch eine Polynomgröße ersetzt werden. Deswegen, L hat ein Ma Protokoll: Merlin sendet die Schaltung als Beweis, und Arthur kann die simulieren IP Protokoll selbst ohne zusätzliche Hilfe.

• Wenn P^#P ⊆ P/poly dann P^#P = Ma.^[6] Der Beweis ist oben ähnlich wie auf einem interaktiven Protokoll für permanent und #P-Completness von Permanent.
• Wenn Nachfolger ⊆ P/poly dann $oder$ (Meyers Theorem), sogar Nachfolger = Ma.
• Wenn Nexptime ⊆ P/poly dann Nexptime = Nachfolger, eben Nexptime = Ma. Umgekehrt, Nexptime = Ma impliziert Nexptime ⊆ P/poly^[7]
• Wenn Exp^Np ⊆ P/poly dann $oder$ (Buhrman, Homer) ^[8]
• Es ist bekannt, dass Ma_Exp, eine exponentielle Version von Ma, ist nicht in enthalten in P/poly.

Beweis: if Ma_Exp ⊆ P/poly dann PSPACE = Ma (siehe oben). Durch Polsterung, Expace = Ma_Exp, deshalb Expace ⊆ P/poly Dies kann jedoch bei Diagonalisierung als falsch erwiesen werden.

Einer der interessantesten Gründe dafür P/poly ist wichtig ist die Eigenschaft, die wenn Np ist keine Teilmenge von P/poly, dann P ≠ Np. Diese Beobachtung war das Zentrum vieler Versuche zu beweisen P ≠ Np. Es ist bekannt, dass für ein zufälliges Orakel A, Np^A ist keine Teilmenge von P^A/poly mit Wahrscheinlichkeit 1.^[1]

P/poly wird auch im Bereich von verwendet Kryptographie. Sicherheit wird oft gegen "gegen" definiert P/poly Gegner. Abgesehen von den meisten praktischen Berechnungsmodellen wie wie BPPDies lässt auch die Möglichkeit zu, dass Gegner eine starke Vorkomputation für Eingaben bis zu einer bestimmten Länge wie bei der Konstruktion von durchführen können Regenbogentische.

Obwohl nicht alle Sprachen in P/poly sind spärliche Sprachen, da ist ein Polynomzeit-Turing-Reduktion von jeder Sprache in P/poly zu einer spärlichen Sprache.^[9]

Probabilistisches Polynom mit begrenztem Erreger ist in P/Poly enthalten

Adlemans Theorem stellt fest, dass das BPP ⊆ P/poly, wo BPP ist der Satz von Problemen, die mit randomisierten Algorithmen mit zweiseitigem Fehler in der Polynomzeit lösbar sind. Ein schwächeres Ergebnis wurde zunächst durch nachgewiesen Leonard Adleman, nämlich das RP ⊆ P/poly;^[10] und dieses Ergebnis wurde auf verallgemeinert BPP ⊆ P/poly durch Bennett und Gill.^[11] Varianten des Theorems zeigen das Bpl ist in L/poly und BIN ist in NP/Poly.

Nachweisen

Lassen L eine Sprache sein in BPP, und lass M(x,r) Seien Sie ein Polynom-Zeit-Algorithmus, der entscheidet L mit Fehler ≤ 1/3 (wo x ist die Eingangszeichenfolge und r ist eine Reihe von zufälligen Bits).

Konstruieren Sie eine neue Maschine M'(x,R), was läuft M 48n Zeiten und nimmt eine Mehrheitsabstimmung der Ergebnisse (wo n ist die Eingangslänge und R ist eine Sequenz von 48n unabhängig zufällig rs). Daher, M' ist auch Polynomzeit und hat eine Fehlerwahrscheinlichkeit ≤ 1///eⁿ bis zum Tschernoff gebunden (sehen BPP). Wenn wir reparieren können R Dann erhalten wir einen deterministischen Algorithmus.

Wenn ${\ displayStyle {\ mbox {bad}} (x)}$ ist definiert als ${\ displayStyle \ {r: m {'} (x, r) {\ text {ist falsch}} \}}$, wir haben:

$oder .}$

Die Eingangsgröße ist n, also gibt es 2ⁿ mögliche Eingaben. So von der Gewerkschaft gebunden, die Wahrscheinlichkeit, dass ein zufälliges R ist schlecht für mindestens einen Eingang x ist

$oder n}}} <1.}$

In Worten die Wahrscheinlichkeit, dass R ist schlecht für einige x ist weniger als 1, daher muss es eine geben R Das ist gut für alle x. Nehmen Sie so ein R Um die Beratungszeichenfolge in unserem zu sein P/poly Algorithmus.

Verweise