Ist BPP vs. P ein echtes Problem, nachdem wir wissen, dass BPP in P / poly liegt?

Wir wissen (seit nunmehr rund 40 Jahren, danke Adleman, Bennet und Gill), dass die Aufnahme BPP P / poly und eine noch stärkere BPP / poly P / poly hält. Das "/ poly" bedeutet, dass wir ungleichmäßig arbeiten (ein separater Schaltkreis für jede Eingangslänge ), während P ohne dieses "/ poly" bedeutet, dass wir eine Turingmaschine für alle möglichen Eingangslängen , die sogar länger sind als beispielsweise = die Anzahl der Sekunden bis zum nächsten "Urknall".⊆ n n $\subseteq$ $\subseteq$ $n$$n$$n$

Frage 1: Was würde ein neuer Beweis (oder ein neuer Disproof) von BPP = P zu unserem Wissen beitragen, nachdem wir BPP P / poly kennen? $\subseteq$

Unter "neu" verstehe ich alle wirklich überraschenden Konsequenzen wie Zusammenbruch / Trennung anderer Komplexitätsklassen. Vergleichen Sie dies mit den Konsequenzen, die der Proof / Disproof von NP P / poly liefern würde. $\subseteq$

[ADDED 08.10.2017]: Eine wirklich überraschende Folge von BPP P wäre, dass, wie von Impagliazzo und Wigderson gezeigt , alle (!) Probleme in E = DTIME hätten Schaltkreise der Größe . Vielen Dank an Ryan für das Zurückrufen dieses Ergebnisses.[ 2 O ( n ) ] 2 o ( n $\not\subseteq$ $[2^{O(n)}]$$2^{o(n)}$

Frage 2: Warum können wir BPP = P nicht nach ähnlichen Gesichtspunkten beweisen wie den Beweis von BPP / poly P / poly? $\subseteq$

Ein "offensichtliches" Hindernis ist das Problem zwischen endlichen und unendlichen Domänen: Boolesche Schaltkreise arbeiten über endliche Domänen, wohingegen Turing-Maschinen über den gesamten Satz $\{0,1\}^*$ von $0$ - $1$ Zeichenketten beliebiger Länge arbeiten. Um probabilistische Boolesche Schaltkreise zu derandomisieren, genügt es also, die Mehrheit der unabhängigen Kopien eines probabilistischen Schaltkreises zu nehmen und Chernoffs Ungleichung zusammen mit der Vereinigungsgrenze anzuwenden. Natürlich funktioniert diese einfache Mehrheitsregel in unendlichen Domänen nicht.

Aber ist das (unendliche Domäne) ein echtes "Hindernis"? Durch die Ergebnisse der statistischen Lerntheorie (VC - Dimension) mit, wir bereits können beweisen , dass BPP / Poly $\subseteq$ P / poly gilt auch für Schaltungen über Arbeits unendlich Domänen, wie Rechenschaltungen (Arbeits über alle reellen Zahlen); siehe zB diese Arbeit von Cucker at al. Bei einem ähnlichen Ansatz müssten wir lediglich zeigen, dass die VC-Dimension von Poly-Time-Turing-Maschinen nicht zu groß sein darf. Hat jemand irgendwelche Versuche gesehen, diesen letzteren Schritt zu machen?

Die Ergebnisse (als einheitliche Wahrscheinlichkeitskonvergenz bekannt ) implizieren dann Folgendes: Wenn für jede Eingabe eine zufällig ausgewählte Funktion (unter einer gewissen Wahrscheinlichkeitsverteilung auf ) erfüllt für eine Konstante , dann kann für alle Eingaben als Mehrheit von berechnet werden einig Funktionen von (festen) . Siehe z. B. Korollar 2 in Hausslers Aufsatz . [Damit dies zutrifft, gibt es einige milde Messbedingungen für ] f ∈ F F P R o b { f ( x ) = f ( x ) } ≥ 1 / 2 + c c > 0 f ( x ) x ∈ X m = O ( v ) F $x\in X$$\mathbf{f}\in F$$F$$\mathrm{Prob}\{\mathbf{f}(x)=f(x)\}\geq 1/2+c$$c>0$$f(x)$$x\in X$$m=O(v)$$F$$F$

Wenn zum Beispiel die Menge aller Polynome durch arithmetische Schaltungen der Größe berechenbar sind , haben alle Polynome in einen Grad von höchstens . Durch die Verwendung von bekannte obere Grenze für die Anzahl der Null-Muster von Polynomen (siehe zB diesem Papier ), kann man zeigen , dass die VC - Dimension ist . Dies impliziert den Einschluss BPP / poly P / poly für arithmetische Schaltungen.f : R n → R ≤ s F D = 2 s F O ( n log D ) = O ( n s ) $F$$f:\mathbb{R}^n\to\mathbb{R}$$\leq s$$F$$D=2^s$$F$$O(n\log D)=O(ns)$$\subseteq$

Ich bin mir nicht sicher, was für eine Antwort das ist, ich gönne mir nur ein paar Gedanken.

Frage 1 könnte gleichermaßen zu P NP und mit einer ähnlichen Antwort gestellt werden - die Techniken / Ideen, die zum Nachweis des Ergebnisses verwendet werden, wären eher der große Durchbruch als die Schlussfolgerung selbst.$\neq$

Zu Frage 2 möchte ich Hintergrundinformationen und Gedanken mitteilen. So ziemlich alle Techniken und Ideen, die wir für BPP = P haben, gehen, soweit mir bekannt ist, über "Derandomisierung": Konstruieren Sie eine PRG, um eine Reihe deterministisch ausgewählter Bits statt zufälliger zu füttern diejenigen, so dass sein Verhalten sehr ähnlich zu seinem Verhalten auf wirklich zufälligen Bits ist. Mit ausreichend guten Pseudozufallsgeneratoren erhalten wir also BPP = P. (Goldreichs "World of BPP = P" beweist, dass jeder Beweis von BPP = P gleichbedeutend damit sein muss.)

Dies ist so ziemlich im Sinne von BPP P / poly, mit der Ausnahme, dass es sich bei PRG um die durch Zauberei erzeugte Hinweiszeichenfolge handelt. Vielleicht ist die beste Antwort auf Ihre Frage 2, dass wir in P keine Magie haben und uns den Ratschlag selbst einfallen lassen müssen. Die Derandomisierung ist auch die Idee hinter dem 2004er-Ergebnis SL = L, das Werkzeuge wie Expandergraphen verwendet.$\subseteq$

Überlegen Sie nun, was ein solcher Beweis für nur einen bestimmten Algorithmus bedeuten würde, den Miller-Rabin-Primalitätstest. Es würde die Existenz eines deterministischen Generators aufzeigen, der eine Folge von Ganzzahlen auswählt, um sie dem Miller-Rabin-Primalitätstest zuzuführen, so dass, wenn und nur wenn alle Ganzzahlen bestanden würden, die ursprüngliche Zahl eine Primzahl war.

Wie ich es verstehe (obwohl ich kein Experte bin), scheint die Frage, ob eine solche Liste existiert und wie klein die Zahlen darin sein können (insbesondere, wenn es ausreicht, alle Zahlen unterhalb einer bestimmten Grenze zu überprüfen), eine ziemlich tiefe Frage zu sein Zahlentheorie und steht in engem Zusammenhang mit Beweisformen der verallgemeinerten Riemannschen Hypothese. Siehe diese Frage . Ich glaube nicht, dass es hier eine formale Implikation gibt, aber es scheint nicht so, als würden wir es nächste Woche als zufällige Miniaturfolge einer viel allgemeineren PRG-Konstruktion erwarten.