Probleme in P mit nachweislich schnelleren randomisierten Algorithmen

$\mathsf{P}$ $k$ $\mathsf{DTIME}(n^k) \subsetneq \mathsf{PTIME}(n^k)$ $\mathsf{PTIME}(f(n))$ die Menge von Sprachen, die durch ein randomisiertes TM mit konstant begrenztem (einseitigem oder zweiseitigem) Fehler in Schritten entscheidbar sind. $f(n)$

Kauft uns der Zufall irgendetwas im Inneren? $\mathsf{P}$ ?

Um es klar zu sagen, ich suche etwas, bei dem der Unterschied asymptotisch ist (vorzugsweise polynomisch, aber ich würde mich für polylogarithmisch entscheiden), nicht nur eine Konstante.

Ich suche im schlimmsten Fall asymptotisch bessere Algorithmen. Algorithmen mit besser erwarteter Komplexität sind nicht das, wonach ich suche. Ich meine randomisierte Algorithmen wie RP oder BPP, nicht ZPP.

algorithms complexity-theory randomized-algorithms aelguindy
quelle

Vielleicht ist "Yaos Technik" das, wonach Sie suchen. Eine kurze Beschreibung finden Sie unter cs.pitt.edu/~kirk/cs2150/yao/yao.html

Wu Yin

@WuYin wenn ich richtig verstehe, geht das in Richtung der unteren Randomisierung von Algorithmen durch das durchschnittliche Fallverhalten von deterministischen Algorithmen. Ich werde genauer darauf eingehen, aber so wie ich es sehe, könnte dies immer nur dazu führen, diese Zufälligkeit zu beweisen hat nicht kaufen uns nichts in

P

$P$ .. Bin ich richtig?

Aelguindy

Zum Auffinden eines Elements in Folge der Länge

n

$n$ mit Rang in [

\frac{n}{4}

$\frac{n}{4}$ ,

\frac{3 * n}{4}

$\frac{3*n}{4}$ ] wir können einfach ein beliebiges Element zurückgeben und es wird mit

korrekt sein

Wahrscheinlichkeit daher sein O (1)! Während ein deterministischer Algorithmus zumindest einen Teil der Eingabe und damit

\frac{1}{2}

$\frac{1}{2}$

Ω (n)

$\Omega(n)$

Rizwanhudda

@ Rizwanhudda Es könnte einige Probleme damit geben. Zunächst suche ich ein Entscheidungsproblem. Zweitens ist im Turing-Modell die Rückgabe eines zufälligen Elements

, da es keinen zufälligen Zugriff gibt. Vielleicht gibt die Maschine immer das erste Element aus? Dennoch ist das erste Problem größer.

Ω (n)

$\Omega (n)$

Aelguindy

Der letzte Absatz ist nicht sinnvoll, da jeder Las Vegas-Algorithmus in einen Monte-Carlo-Algorithmus konvertiert werden kann.

Tsuyoshi Ito

Antworten:

Beim Testen der polynomiellen Identität wird ein randomisierter polynomieller Zeitalgorithmus zugelassen (siehe das Schwartz-Zippel-Lemma ), für den es derzeit weder einen deterministischen polynomiellen Zeit- noch einen subexponentiellen Zeitalgorithmus gibt.

Spielbaumauswertung Betrachten Sie einen vollständigen Binärbaum mit Blattknoten, die jeweils einen 0/1-Wert speichern. Die internen Knoten enthalten ODER / UND-Gatter in alternativen Ebenen. Mit dem Gegenargument kann bewiesen werden, dass jeder deterministische Algorithmusim schlimmsten Fall Blattknotenuntersuchen müsste. Es gibt jedoch einen einfachen randomisierten Algorithmus, der eine erwartete Laufzeit von Schauen Sie sich die Folien 14-27 des Vortrags an. $n$ $\Omega{(n)}$ $O(n^{0.793})$

Oblivious routing on a hypercube Betrachten Sie einen Würfel in Dimensionen mit Eckpunkten. Jeder Vertex hat ein Datenpaket und ein Ziel, an das er das Paket schließlich übermitteln möchte. Das Ziel aller Pakete ist unterschiedlich. Auch dafür wurde bewiesen, dass jede deterministische Routing-Strategie $n$ $N=2^n$ Schritte. Es gibt jedoch eine einfache randomisierte Strategie, diemit hoher Wahrscheinlichkeitinerwarteten-Schrittenendet. $\Omega{\big(\sqrt{\frac{N}{n}}\big)}$ $O(n)$

Es ist zu beachten, dass in randomisierten Algorithmen die erwarteten Kosten mit hoher Wahrscheinlichkeit (wie zum Beispiel für $E(F(n))$ ) entspricht dem schlechtesten Fall in der Praxis. $Pr[F(n) > 10 \cdot E(F(n))] < \frac{1}{n^2}$

rizwanhudda
quelle

Außerdem berücksichtigt für Matrizen Prüfung

und

, wenn

. Wir kennen derzeit keinen

-Algorithmus, wir kennen einen randomisierten

-Algorithmus. Der Punkt ist, gibt es Probleme, für die wir beweisen können , dass randomisierte Algorithmen besser sind?

A

$A$

B

$B$

C

$C$

A B = C

$A B = C$

o (2^{2.3})

$o(2^{2.3})$

O (n^{2})

$O(n^2)$

Aelguindy

@aelguindy Ich verstehe deinen Standpunkt. Für PIT ist der bekannteste deterministische Algorithmus jedoch exponentiell. Und die Derandomisierung von PIT ist ein wichtiges offenes Problem in Theoretical CS.

Rizwanhudda

Ich habe dem Post Game Tree Evaluation und Hypercube Routing hinzugefügt, für die randomisierte Algorithmen nachweislich besser sind als deterministische Gegenstücke.

Rizwanhudda

OK, wenn ich die Game Tree-Auswertung richtig verstehe, läuft sie in erwarteten

, oder? Ich meine, es gibt Fälle, in denen es in

läuft . Gilt das auch für das dritte Beispiel? Ich erlaube keine bessere erwartete Zeit, ich suche eine bessere Worst-Case-Komplexität, erlaubte Fehler in der Ausgabe.

O (n^{0.793})

$O(n^{0.793})$

Ω (n)

$\Omega(n)$

Aelguindy

Sie sind also im schlimmsten Fall nicht besser. So sehr ich die Beispiele schätze, fürchte ich, dass das nicht genau das ist, wonach ich suche. Die Beispiele waren jedoch sehr aufschlussreich!

Aelguindy

Die Untersuchung des Worst-Case ist für randomisierte Algorithmen bedeutungslos. Die Laufzeit im ungünstigsten Fall ist häufig nicht nur unendlich, sondern kann auch deterministische Algorithmen in dieser Metrik nicht übertreffen.

Betrachten Sie jeden randomisierten Algorithmus . Erhalten Sie einen deterministischen Algorithmus indem Sie das Zufallsband für auf festlegen . Dann ist für alle . $A$ $B$ $A$ $0^\infty$ $T_B(n) \leq T_A(n)$ $n$

Raphael
quelle

Es gibt viele Probleme, bei denen wir einen effizienten randomisierten Algorithmus kennen, und wir kennen keinen deterministischen Algorithmus, von dem wir nachweisen können, dass er effizient ist. Dies kann jedoch auf Mängel in unserer Fähigkeit zurückzuführen sein, eher die Komplexität als einen fundamentalen Unterschied zu beweisen.

Auf der Grundlage Ihres Kommentars möchten Sie anscheinend fragen, ob es ein Problem mit einem effizienten randomisierten Algorithmus gibt, und wir können nachweisen, dass es keinen deterministischen Algorithmus mit vergleichbarer Effizienz gibt. Ich kenne kein solches Problem.

In der Tat gibt es hinreichende Gründe für den Verdacht, dass solche Probleme unwahrscheinlich sind. Heuristisch würde das Vorhandensein eines solchen Problems wahrscheinlich bedeuten, dass eine sichere Kryptographie unmöglich ist. Das scheint ein ziemlich unplausibles Ergebnis zu sein.

Was ist die Verbindung, fragst du? Betrachten Sie einen beliebigen randomisierten Algorithmus , der ein Problem effizient löst. Es basiert auf zufälligen Münzen: zufälligen Bits, die aus einer echten Zufallsquelle stammen. Nehmen wir nun an, wir nehmen einen Pseudozufallsgenerator mit kryptografischer Qualität und ersetzen die echte Zufallsquelle durch die Ausgabe des Pseudozufallsgenerators. Rufen Sie den resultierenden Algorithmus . Es ist zu beachten, dass ein deterministischer Algorithmus ist und seine Laufzeit ungefähr gleich . $A$ $A'$ $A'$ $A$

Wenn das kryptografische PRNG sicher ist, sollten wir heuristisch erwarten dass ein guter Algorithmus ist, wenn ist: $A'$ $A$

Wenn beispielsweise ein Las Vegas-Algorithmus ist (er gibt immer die richtige Antwort aus und endet schnell mit hoher Wahrscheinlichkeit), dann ist ein ziemlich guter deterministischer Algorithmus (gibt immer die richtige Antwort aus und endet schnell für die meisten Eingaben). . $A$ $A'$
Wenn ein Monte-Carlo-Algorithmus ist (deterministische Laufzeit und Ausgabe der richtigen Antwort mit einer Wahrscheinlichkeit von mindestens ), dann ist ein ziemlich guter deterministischer Algorithmus (deterministische Laufzeit und Ausgabe der richtigen Antwort auf einen Bruchteil aller Eingaben). $A'$ $1-\varepsilon$ $A$ $1-\varepsilon$

Wenn also der kryptografische PRNG sicher ist und ein effizienter randomisierter Algorithmus vorliegt, erhalten Sie einen ziemlich guten deterministischen Algorithmus. Nun gibt es viele Konstruktionen von kryptografischen PRNGs, die bei bestimmten kryptografischen Annahmen als sicher gelten. In der Praxis wird allgemein angenommen, dass diese kryptografischen Annahmen zutreffen: Zumindest für sicheren Handel und Transaktionen müssen sie zutreffen, sodass wir offenbar bereit sind, große Summen auf sichere Kryptografie zu setzen. Diese Umwandlung kann nur fehlschlagen, wenn kein kryptografisches PRNG vorhanden ist, was wiederum impliziert, dass eine sichere Kryptografie unmöglich ist. Wir haben zwar keinen Beweis dafür, dass dies nicht der Fall ist, aber es scheint ein unwahrscheinliches Ergebnis zu sein.

Konstruktionsdetails: So funktioniert . Bei Eingabe wird ein Startwert für das kryptografische PRNG als Funktion von (z. B. durch Hashing von ) und anschließend unter Verwendung der Ausgabe des kryptografischen PRNG als Münzen für simuliert . Eine spezielle Instanziierung wäre beispielsweise, und dann als Startwert für AES256 im Zählermodus oder ein anderes kryptografisches PRNG zu verwenden. Wir können die obigen Aussagen nach dem Zufalls-Orakel-Modell beweisen. $A'$ $x$ $x$ $x$ $A(x)$ $A$ $k=\text{SHA256}(x)$ $k$

Wenn Sie mit der Idee unzufrieden sind, dass bei einem kleinen Teil der Eingaben falsche Ergebnisse ausgibt, kann dies behoben werden. Wenn Sie mehrmals wiederholen und eine Mehrheitsentscheidung treffen, nimmt die Fehlerwahrscheinlichkeit in der Anzahl der Iterationen exponentiell schnell ab. Also, durch eine konstante Anzahl von Malen iteriert, können Sie die Fehlerwahrscheinlichkeit erhalten unten zu , was die Chancen bedeutet , dass Sie über einen Eingang laufen $A'$ $A'$ $\varepsilon$ $1/2^{256}$ $x$ Wo der Algorithmus die falsche Antwort ausgibt, sind sie verschwindend klein (weniger als die Wahrscheinlichkeit, mehrmals hintereinander vom Blitz getroffen zu werden). Darüber hinaus mit dem Bau habe ich oben, um die Chancen , dass ein Gegner kann selbst findet einen Eingang , wo kann die falsche Antwort gibt sehr klein gemacht werden, so dass erfordern würde die Sicherheit des SHA256 Hash zu brechen. (Aus technischer Sicht muss das Zufalls-Orakel-Modell dies rechtfertigen. Dies bedeutet, dass so gewählt werden muss , dass es von SHA256 "unabhängig" ist und keine mit SHA256 verwandten Hardcode-Berechnungen enthält, aber fast alle realen Algorithmen erfüllen diese Anforderung .) $x$ $A'$ $A$

$A$ $\Theta(n)$ $1/2^n$ $n$ $x$ $n$ $A'$ $1/2^n$ $2^n$ $n$ $A$ $A'$ $A'$ $A$ $t(n)$ $A'$ $\Theta(n \cdot t(n))$ $A'$ ist etwas langsamer als $A$ aber nicht zu viel langsamer. Dies ist der Inhalt von Adlemans Beweis, dass BPP in P / poly enthalten ist. Aus praktischen Gründen ist dies wahrscheinlich übertrieben, aber wenn Sie saubere Beweise bevorzugen, die kryptografische Annahmen vermeiden, oder wenn Sie dies aus der Sicht eines Theoretikers betrachten, wird Ihnen diese Version möglicherweise besser gefallen.

For more details on the latter theoretical considerations and additional problems where we know of an efficient randomized algorithm but we don't know of any deterministic algorithm that we can prove is efficient, see /cstheory//q/31195/5038

In summary: For any problem where we know an efficient randomized algorithm, we also know of a deterministic algorithm that seems likely to be efficient in practice -- but at present we don't know how to prove that it is efficient. One possible interpretation is that we're just not very good at proving stuff about algorithms.

D.W.
quelle