Beispiele für eine erfolgreiche Derandomisierung von BPP zu P

Was sind einige wichtige Beispiele für eine erfolgreiche Derandomisierung oder zumindest Fortschritte bei der Darstellung konkreter Belege für das Ziel (nicht die Härte-Zufalls-Verbindung)? $P=BPP$

Das einzige Beispiel, das mir in den Sinn kommt, ist das Testen der deterministischen Polynom-Zeit-Primalität nach AKS (auch dafür gab es eine Methodik, die GRH voraussetzte). Welchen konkreten Beweis haben wir für die Derandomisierung (wiederum nicht für die Härte oder die Orakelverbindung)?

Bitte behalten Sie nur Beispiele bei, bei denen eine Verbesserung der Zeitkomplexität von randomisiertem Poly zu deterministischem Poly oder etwas gezeigt wurde, das für bestimmte Probleme sehr nahe ist.

Das Folgende ist eher ein Kommentar und ich weiß nicht viel, es wird dieser Abfrage helfen.

Chazelle hat eine sehr interessante Aussage in http://www.cs.princeton.edu/~chazelle/linernotes.html unter "The Discrepancy Method: Randomness and Complexity (Cambridge University Press, 2000)".

„Für mich war es eine unendliche Faszination, dass ein tieferes Verständnis des deterministischen Rechnens die Beherrschung der Randomisierung erfordern sollte. Ich habe dieses Buch geschrieben, um diese starke Verbindung zu veranschaulichen. Die effizientesten Algorithmen, angefangen von minimalen Spannbäumen über lineare Programmierung bis hin zu Delaunay-Triangulationen, sind häufig die Derandomisierung probabilistischer Lösungen. Die Diskrepanzmethode beleuchtet eine der fruchtbarsten Fragen der gesamten Informatik: Wenn Sie der Meinung sind, dass Sie zufällige Bits benötigen, teilen Sie uns bitte mit, warum. '

cc.complexity-theory big-list randomized-algorithms derandomization pseudorandom-generators
quelle

Viele Algorithmen können mithilfe allgemeiner Techniken wie der Methode der bedingten Erwartungen, der Methode der pessimistischen Schätzer und der Verwendung begrenzter unabhängiger Stichprobenräume derandomisiert werden. In der Tat sind Primalitätstests und Polynomidentitätstests so berühmt, weil sie seltene Beispiele für natürliche Funktionen sind, die Standard-Derandomisierungstechniken widerstehen.

Sasho Nikolov

@SashoNikolov danke kann der Kommentar als vollständige Antwort auf einige Beispiele erweitert werden. Ist auch die Härte-Zufälligkeits-Verbindung über die Schaltungskomplexität der einzige Grund, warum Leute glauben,

P = B P P

$P=BPP$

Ich denke, das ist ein bisschen zu grundlegend für eine Antwort. Weitere Informationen und Beispiele finden Sie im Kapitel zur Derandomisierung in Alon-Spencer. Es werden die drei von mir genannten Techniken behandelt.

Sasho Nikolov

Das Interessante an der Klasse BPP ist, dass für ihre theoretische Definition zufällige Eingabebits erforderlich sind, die mithilfe von De-Randomization- und schwachen Kolomogrov-Zufallsmaßen leicht gezeigt werden können und nicht in endlichen Domänen existieren. Ich weiß nicht, wie Menschen mit dieser Inkonsistenz leben können. Ich selbst glaube nicht, dass es eine explizite Klasse BPP gibt (entweder NP oder P).

Antworten:

. $SL = L$

steht für randomisierte logspace und ist eine kleinere Version des Problems . Ein wichtiger Schritt war der Beweis von Reingold in '04 ("Ungerichtete ST-Konnektivität in Logspace"), dass , wobei für "symmetrisch" steht und eine Zwischenklasse zwischen und . $RL$ $RL=L$ $RP=P$ $SL = L$ $S$ $SL$ $RL$ $L$

Die Idee ist, dass Sie sich eine Turing-Maschine mit randomisiertem Logspace als einen polynomgroßen gerichteten Graphen vorstellen können, bei dem Knoten Zustände der Maschine sind und ein RL-Algorithmus eine zufällige Wanderung mit guten Eigenschaften durchführt. SL entspricht ungerichteten Graphen dieser Form. Reingolds Beweis basiert auf der Arbeit an Expandergraphen, insbesondere Reingold, Vadhan und Wigdersons "Zick-Zack-Produkt", um einen beliebigen Gang auf einem ungerichteten Graphen mit guten Eigenschaften zu machen und ihn in einen pseudozufälligen Gang umzuwandeln, der diese Eigenschaften beibehält.

bearbeiten diese Frage wurde veröffentlicht, bevor die Frage explizit geändert wurde, um sich ausschließlich auf P vs BPP zu konzentrieren ... Ich lasse es hier, weil es interessant zu sein scheint.

usul
quelle

Bitte nicht Die Antwort ist interessant.

Emil Jeřábek unterstützt Monica am

Hallo @Student., Ich denke, die Leute, die sich mit der Frage nach Beispielen für erfolgreiche Derandomisierung beschäftigen, werden an dieser Antwort interessiert sein. Ich werde sie daher beibehalten, ohne dass dies eine Missachtung Ihrer Ziele bedeutet (die erst später bearbeitet wurden, um die zeitliche Komplexität zu spezifizieren). )

usul

Ich sollte auch sagen, dass Fragen und Antworten auf dieser Website so formuliert werden sollen, dass sie im Allgemeinen für zukünftige Besucher als Referenzressource nützlich sind und nicht nur den jeweiligen Zielen des Plakats entsprechen. Ich finde die Frage ohne künstliche Einschränkung der Zeitkomplexität und BPP viel nützlicher.

Emil Jeřábek unterstützt Monica am

@ EmilJeřábek Ok, danke, wir werden Usuls Beitrag so lassen, wie er hier ist.

@usul 'Die Idee ist, dass Sie sich eine Turing-Maschine mit randomisiertem Logspace als einen polynomgroßen gerichteten Graphen vorstellen können.' Gibt es eine passende Intuition, die für NL funktioniert? Ich weiß, dass L nicht NL ist, sondern PSPACE = NPSPACE, und daher kann der Raum anders sein als die Zeit.

T ....

Grundsätzlich gibt es bei BPP nur ein interessantes Problem, von dem nicht bekannt ist, dass es bei P auftritt: Polynomial Identity Testing, vorausgesetzt, eine algebraische Schaltung ist das Polynom, das sie identisch mit Null erzeugt. Impagliazzo und Kabanets zeigen, dass PIT in P einige Schaltkreisuntergrenzen implizieren würde. Daher sind untere Schaltkreisgrenzen der einzige Grund (aber ein ziemlich guter Grund), aus dem wir glauben, dass P = BPP.

Lance Fortnow
quelle

Obwohl ich Ihnen auf hohem Niveau zustimme, denke ich, dass die Fülle randomisierter Algorithmen in der rechnergestützten Gruppentheorie eine weitere engmaschige Klasse interessanter Derandomisierungsfragen nahe legt, die sich nicht auf PIT zu reduzieren scheinen. Während die meisten davon eher Funktionen als Entscheidungsprobleme sind, können einige von ihnen in BPP als interessante Entscheidungsprobleme umformuliert werden

Joshua Grochow

O (f (n))

$O(f(n))$

O (f (n))

$O(f(n))$

B P P

$BPP$

B P P

$BPP$

f (n)

$f(n)$

P = B P P

$P=BPP$ Vermutung betroffen, wenn deterministische und erwartete randomisierte Lücke für diese Algorithmen nicht geschlossen werden kann?

T ....

Neben dem Testen der Identität von Polynomen besteht ein weiteres sehr wichtiges Problem, das bei BPP, aber nicht bei P bekannt ist, darin, die Permanenz einer nicht-negativen Matrix oder sogar die Anzahl perfekter Übereinstimmungen in einem Diagramm zu approximieren. Es gibt einen randomisierten Polyzeit-Algorithmus, um diese Zahlen innerhalb eines (1 + eps) -Faktors zu approximieren, während die besten deterministischen Algorithmen nur ~ 2 ^ n-Faktor-Approximationen erzielen.

Während permanent das Hauptbeispiel ist, gibt es viele ungefähre Zählprobleme, bei denen eine große Lücke zwischen randomisierten Algorithmen (normalerweise basierend auf 'MCMC'-Methoden) und deterministischen Algorithmen besteht.

Ein anderes Problem in ähnlicher Weise ist die Approximation des Volumens eines explizit gegebenen konvexen Körpers (beispielsweise eines Polyeders, das durch eine Sammlung linearer Ungleichungen beschrieben wird).

Raghu Meka
quelle

Eine Subtilität in P vs BPP, die ich besser verstehen möchte, ist der Unterschied zwischen Funktionsproblemen und Entscheidungsproblemen. Es kann sein, dass es viele Funktionsprobleme gibt, die (in gewissem Sinne) zufällig, aber nicht deterministisch in der Polynomzeit lösbar sind, dennoch ist P = BPP. Ihre Beispiele lassen sich wahrscheinlich leicht auf Entscheidungsprobleme übertragen, oder?

USUL

Entscheidungsprobleme im Vergleich zu Funktionsproblemen sind etwas subtiler als in der NP-Welt, es ist jedoch noch viel bekannt: Zum Beispiel enthält dieser Aufsatz in Abschnitt 3 ein Beispiel für ein "randomisiertes polyzeitlösbares Suchproblem", das nicht einmal entscheidbar ist. Aber wenn die Funktion eins zu eins ist, dann impliziert P = BPP ein "randomisiertes polyzeitlösbares Funktionsproblem" mit einem deterministischen polyzeitalgorithmus (das Papier gibt auch viele weitere Beispiele).

Joe Bebel