Was ist die schnellste bekannte BPP-Simulation mit Las Vegas-Algorithmen?

$\mathsf{BPP}$ und $\mathsf{ZPP}$ sind zwei grundlegende probabilistische Komplexitätsklassen.

$\mathsf{BPP}$ ist die Klasse von Sprachen, die durch probabilistische Polynomzeit-Turing-Algorithmen bestimmt wird, bei denen die Wahrscheinlichkeit, dass der Algorithmus eine falsche Antwort zurückgibt, begrenzt ist, dh die Fehlerwahrscheinlichkeit beträgt höchstens $\frac{1}{3}$ (sowohl für JA als auch für NEIN).

Andererseits können $\mathsf{ZPP}$ -Algorithmen als solche probabilistischen Algorithmen angesehen werden, die niemals eine falsche Antwort zurückgeben, wenn sie eine Antwort zurückgeben, die korrekt ist. Ihre Laufzeit ist jedoch nicht durch ein Polynom begrenzt, sondern läuft im erwarteten Polynom.

Sei $\mathsf{ZPTime}(f)$ die Sprachklasse, die durch probabilistische Algorithmen mit einer Fehlerwahrscheinlichkeit von Null und der erwarteten Laufzeit $f$ . Diese werden auch als Las Vegas-Algorithmen und $\mathsf{ZPP} = \mathsf{ZPTime}(n^{O(1)})$ .

Meine Frage ist , was am besten wissen Simulation ist $\mathsf{BPP}$ Algorithmen Algorithmen Las Vegas mit? Können wir sie in subexponentieller erwarteter Zeit simulieren? Gibt es eine bekannte Verbesserung gegenüber der trivialen Brute-Force-Simulation, die exponentielle Zeit benötigt?

Wissen wir formal, ob $\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{O(n^{\epsilon})})$ oder $\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{n-n^{\epsilon}})$ für einige $\epsilon>0$ ?

cc.complexity-theory complexity-classes randomness randomized-algorithms echuly
quelle

Was ist n, die Länge der Eingabe? Warum können wir in

akzeptieren ?

2^{n}

$2^n$

Domotorp

ist dasselbe wie

2^{p o l y (n) - n^{ϵ}}

$2^{\mathrm{poly}(n)-n^\epsilon}$

2^{p o l y (n)}

$2^{\mathrm{poly}(n)}$

Emil Jeřábek

Ich finde die Frage sehr interessant. Ich habe die Frage bearbeitet, um sie lesbarer und präziser zu machen. Fühlen Sie sich frei, weiter zu bearbeiten. ps: Ich vermute, dass Sie wahrscheinlich die polynomiell vielen zufälligen Bits berücksichtigen wollten, die vom BPP-Algorithmus als Parameter für die Simulationszeit verwendet werden, aber wie Emil hervorhebt, ergibt das, was Sie geschrieben haben,

. Wenn Sie möchten, dass Sie BPP durch eine bestimmte Klasse von Algorithmen für begrenzte Fehlerwahrscheinlichkeiten ersetzen, die einen Parameter für die Anzahl der vom Algorithmus verwendeten Zufallsbits enthalten.

2^{p o l y (n)}

$2^{poly(n)}$

Kaveh

Sie können fragen, ob wir einen BPP-Algorithmus simulieren können, der

Zufallsbits in

da die Brute-Force-Simulation in

Zeit.

r (n)

$r(n)$

Z P T i m e (2^{r (n) - n^{ϵ}} n^{O (1)})

$\mathsf{ZPTime}(2^{r(n)-n^\epsilon}n^{O(1)})$

2^{r (n)} n^{O (1)}

$2^{r(n)}n^{O(1)}$

Kaveh

Antworten:

Zuerst wird beobachten , daß , wenn für eine Konstante , dann . (Beweis durch nichtdeterministische Zeithierarchie.) Der Nachweis einer solchen Einbeziehung wäre daher nicht nur deshalb von Bedeutung, weil es sich um eine verbesserte Simulation handelt, sondern würde auch den ersten Fortschritt bei randomisierten Zeituntergrenzen seit Jahrzehnten bringen. $\mathsf{BPP} \subseteq \mathsf{ZPTIME}[2^{n^{c}}]$ $c$ $\mathsf{BPP} \neq \mathsf{NEXP}$

Als nächstes betrachten wir die Klasse $\mathsf{PromiseBPP}$ , für die das folgende Problem " -hard" ist: $\mathsf{PromiseBPP}$

Schaltung Approximation Probability Problem (CAPP): Bei einer Schaltung , die Ausgangsakzeptanzwahrscheinlichkeit von auf innerhalb eines additiven Faktors. $C$ $C$ $1/6$

$2^{n^{\varepsilon}}$ $n$ $C$ $\mathsf{NEXP} \not\subset \mathsf{P/poly}$ $C$ $k$ $n$ $2^{k-\omega(\log k)}\mathrm{poly}(n)$ $\mathsf{NEXP} \not\subset \mathsf{P/poly}$ . Das heißt, es gibt sicherlich Probleme, die mit der Zufälligkeit von zweiseitigen Fehlern berechenbar sind, für die Null-Fehler-Algorithmen, die die erschöpfende Suche sogar geringfügig übertreffen, implizite untere Grenzen implizieren würden. Ich glaube, dies sollte als mögliche Methode zum Nachweis von Untergrenzen interpretiert werden. Ihr Kilometerstand kann variieren.

Beachten Sie, dass sogar der Nachweis von ebenfalls offen ist und dass dies auch Untergrenzen implizieren würde: von Kabanets und Impagliazzo 2004, wenn Polynomidentität Das Testen (ein -Problem) befindet sich in für alle , dann haben wir Untergrenzen für entweder Permanent oder . Kürzlich (in STOC'13) habe ich bedingungslos bewiesen, dass entweder oder hat $\mathsf{RP} \subseteq \mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ $\mathsf{coRP}$ $\mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ $\varepsilon > 0$ $\mathsf{NEXP}$ $\mathsf{BPP} \subseteq \mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^{\varepsilon}$ $\mathsf{RTIME}[2^n]$ $n^c$ Größenschaltungen, die auf der "easy zeugen" -Methode von Kabanets aufbauen. Dies impliziert zwei Dinge:

Es gibt ein , so dass für alle , ist bedingungslos in - das ist über die beste unbedingten Derandomisierung von in , die wir bisher kennen. $c$ $\varepsilon > 0$ $\mathsf{RP}$ $\mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^c$ $\mathsf{RP/BPP}$ $\mathsf{ZPP}$
Um interessante subexponentielle Simulationen von , müssen Sie "nur" davon ausgehen, dass keine Schaltungen mit fester Polynomgröße hat. $\mathsf{BPP}$ $\mathsf{RTIME}[2^n]$

Ryan Williams
quelle

Vielen Dank an Niel, dass sie sich die Zeit genommen haben, meine Antwort lesbar zu machen :)

Ryan Williams

Ryan, ich glaube, ich werde gleich eine sehr dumme Frage stellen, aber jetzt gehe ich: Warum brauchst du in deinem ersten Satz "für alle "? Bedeutet die BPP-Teilmenge von ZPTIME (2 ^ (n ^ c)) für einige c nicht, dass die BPP-Teilmenge von RTIME (2 ^ (n ^ c)) und damit NTIME (2 ^ (n ^ c)) festgelegt ist, also ist BPP ungleich NEXP oder anderweitig NTIME (2 ^ (2n ^ c)) ist eine Teilmenge von NTIME (2 ^ (n ^ c))?

ϵ

$\epsilon$

Sasho Nikolov

nicht dumm - tatsächlich reicht für einige für , danke, dass Sie darauf hingewiesen haben. Für die anderen Konsequenzen sind jedoch subexponentielle Zeitalgorithmen erforderlich.

B P P \subseteq N T I M E (2^{n^{c}})

$BPP \subseteq NTIME(2^{n^c})$

c

$c$

B P P \neq N E X P

$BPP \neq NEXP$

Ryan Williams

Ryan: Wenn ich Ihr Papier verstehen wollte, welches Buch / welche Papiere über die Komplexität von Schaltkreisen empfehlen Sie, sich damit vertraut zu machen?

T ....

Hallo Arul, zum Glück hat mir Bill Gasarch diese Frage vor einiger Zeit gestellt und die folgende Webseite mit Links eingerichtet: cs.umd.edu/~gasarch/ryan/ryan.html

Ryan Williams

Es hängt davon ab, welche Annahmen Sie treffen möchten.

$E \not\subseteq SIZE(2^{\varepsilon n})$ $P = BPP$ $BPP = ZPP$ $L \in BPP$

$ZPE \not\subseteq \rm{io-DTIME}(2^{\varepsilon n})$ $BPP = ZPP$

Oder Meir
quelle

Abgesehen von Fortschritten bei der Derandomisierung scheint mir die Anforderung, dass die Las Vegas-Maschine keine Fehler macht, von entscheidender Bedeutung zu sein, so dass Zufälligkeit in diesem Fall kaum oder gar keinen Nutzen bringt.

$L$ $A$ $x \in \{0,1\}^n$ $r \in \{0,1\}^{N(n)}$

\underset{r}{Pr} (A accepts (x, r)) ⩾ \frac{2}{3} or \underset{r}{Pr} (A accepts (x, r)) ⩽ \frac{1}{3}

$\Pr_r(\text{$A$ accepts $(x,r)$}) \geqslant \tfrac{2}{3} \quad\text{or}\quad \Pr_r(\text{$A$ accepts $(x,r)$}) \leqslant \tfrac{1}{3}$

A

$A$

A^{'}

$A'$

A^{'} (r) = A (x, r)

$A'(r) = A(x,r)$ und angesichts des Versprechens, dass eine Ausgabe für mindestens doppelt so viele Eingaben wie die entgegengesetzte Ausgabe ergibt , bestimmen Sie welche Ausgabe ist häufiger.

A^{'}

$A'$

a \in {0, 1}

$a \in \{0,1\}$

1 - a

$1-a$

Obwohl die Las Vegas-Maschine zufällige Techniken verwenden kann, können wir, wenn wir tatsächlich gezwungen sind, als Orakel zu behandeln , sehen, dass die einzige Strategie, die einer Las Vegas-Maschine zur Verfügung steht, darin besteht, eine relativ gründliche (wenn auch nicht erschöpfende) Untersuchung der zufällige Zeichenfolgen , um zu sehen, welche Antwort für jede gegeben wird. Es kann nur sicher sein, ob es mehr als verschiedene Zeichenfolgen die alle zur gleichen Ausgabe führen; Andernfalls kann es mit geringer Wahrscheinlichkeit (aber nicht Null!) unglücklich sein, eine nicht repräsentative Stichprobe der möglichen Ausgaben zu erhalten. Um einen Fehler von Null zu erhalten, müssen mindestens Eingänge . $A'$ $r$ $2^{N(n)}\!/3$ $r$ $2^{N(n)}\!/3$ $r$

Da die Las Vegas-Maschine mindestens einen konstanten Bruchteil aller möglichen Zufallszeichenfolgen , sind wir asymptotisch nicht besser dran, als wenn wir alle möglichen Zufallszeichenfolgen deterministisch getestet hätten. Wir erhalten keinen asymptotischen Vorteil bei der zufälligen Simulation von BPP- Algorithmen in einer Null-Fehler-Einstellung, über das hinaus, was wir mit Brute-Force deterministisch tun können. $r$

Beachten Sie, dass dasselbe Argument zu einer zwischen BPP und ZPP führt , dh es gibt ein Orakel so dass weil der ZPP- Algorithmus exponentielle Zeit benötigt, während a Der BPP- Algorithmus kann die Frage nach dem Orakel in einer einzigen Abfrage lösen und mit einem begrenzten Fehler erfolgreich sein. Es sagt Ihnen jedoch nicht mehr als das, was Sie bereits vermutet haben (dass der Simulationsaufwand möglicherweise schlechter als das Polynom ist) oder dass die Asymptotik genauso schlecht ist wie eine naive deterministische Simulation. $A$

{Z P P}^{A} ⫋ {B P P}^{A}

$\mathsf{ZPP}^A \subsetneqq \mathsf{BPP}^A$

Niel de Beaudrap
quelle

Korrigieren Sie mich, wenn ich falsch liege: Sie geben eine intuitive Begründung an, warum eine Derandomisierung unmöglich erscheint, aber wir wissen, dass BPP, ZPP und P unter vernünftigen Annahmen alle dasselbe sind. so dass Intuition nicht unbedingt gut ist

Sasho Nikolov

Überhaupt nicht. Derandomisierung wäre vermutlich ein Einblick in die Simulation von BPP durch P , nicht wahr ? Ich beschreibe nur, wie er, wenn er bedingungslose Ergebnisse will, die die Struktur des Algorithmus selbst nicht ausnutzen, genauso gut eine deterministische Simulation wie eine randomisierte Null-Fehler-Simulation durchführen kann. Oder stimmt etwas mit dieser Erklärung nicht?

Niel de Beaudrap

Ich denke, alles, was Sie sagen, ist, dass die naive Brute-Force-Simulation von BPP durch ZPP nicht viel schneller ist als die naive Brute-Force-Simulation von BPP durch P., aber ich kann nicht sehen, was das zeigen soll. Für mich ist das so, als würde jemand fragen, was der schnellste Algorithmus ist, um eine maximale Übereinstimmung zu finden, und als Antwort erhalten: "Nun, wenn er keinen Einblick in die Struktur der Übereinstimmungen hat, ist es exponentielle Zeit." Die Frage ist, ob es einige bekannte Einblicke in die Struktur von BPP gibt, die eine effiziente ZPP-Simulation ermöglichen

Sasho Nikolov

@SashoNikolov: Es war nicht wirklich als tiefer Einblick gedacht. Nach dem Wortlaut der Frage schien es mir eine Grenze für die Migration zu CS.SE zu sein. Ich habe mich entschlossen, es wörtlich zu beantworten: Soweit wir wissen , ist die effizienteste erwartete Laufzeit von Las Vegas Machine, die eine Sprache L∈BPP akzeptiert, nicht viel besser als eine deterministische Maschine, die die Möglichkeiten von Brute-Force untersucht. Die Antworten, die besagen, dass es sich bei bestimmten Bedingungen möglicherweise um eine Polynomobergrenze handelt, sind ausgezeichnet und informativ, und ich stimme dafür. aber ich spreche die eigentliche Frage an.

Niel de Beaudrap

Ich denke, das ist eine nette Antwort (jetzt auch nach dem Bearbeiten besser lesbar). Wir haben kein bedingtes Ergebnis wie "P = ZPP impliziert P = BPP" oder "ZPP = BPP impliziert P = BPP", daher ist es immer noch möglich, dass wir BPP durch ZP-Algorithmen schneller simulieren können als mit deterministischen Algorithmen. Das Relativierungsergebnis scheint jedoch zu implizieren, dass dies durch keine Relativierungssimulation geschehen kann. Verstehe ich das richtig?

Kaveh