Las Vegas gegen Monte Carlo randomisierte Entscheidungsbaumkomplexität

13

Hintergrund:

Entscheidungsbaumkomplexität oder Abfragekomplexität ist ein einfaches Berechnungsmodell, das wie folgt definiert ist. Sei eine Boolesche Funktion. Die deterministische Abfragekomplexität von , bezeichnet mit , ist die minimale Anzahl von Bits der Eingabe , die (im schlimmsten Fall) von einem deterministischen Algorithmus gelesen werden müssen berechnet . Beachten Sie, dass das Maß für die Komplexität die Anzahl der Bits der Eingabe ist, die gelesen werden. Alle anderen Berechnungen sind kostenlos.f:{0,1}n{0,1}fD(f)x{0,1}nf(x)

In ähnlicher Weise definieren wir die zufällige Las Vegas-Abfragekomplexität von , die mit R 0 ( f ) bezeichnet wird , als die minimale Anzahl von Eingabebits, die von einem zufälligen Null-Fehler-Algorithmus, der f ( x ) berechnet, erwartungsgemäß gelesen werden müssen . Ein Null-Fehler-Algorithmus gibt immer die richtige Antwort aus, aber die Anzahl der von ihm gelesenen Eingangsbits hängt von der internen Zufälligkeit des Algorithmus ab. (Deshalb messen wir die erwartete Anzahl der gelesenen Eingangsbits.)fR0(f)f(x)

Wir definieren die mit R 2 ( f ) bezeichnete Monte-Carlo-Komplexität randomisierter Abfragen von als die minimale Anzahl von Eingabebits, die von einem Randomized-Error-Randomized-Algorithmus gelesen werden müssen, der f ( x ) berechnet . Ein begrenzter Fehleralgorithmus gibt immer eine Antwort am Ende, aber es muss nur mit einer Wahrscheinlichkeit von mehr als korrekt sein 2 / 3 (sagen wir).fR2(f)f(x)2/3


Frage

Was ist über die Frage bekannt, ob

?R0(f)=Θ(R2(f))

Es ist bekannt, dass

R0(f)=Ω(R2(f))

weil Monte-Carlo-Algorithmen mindestens so leistungsfähig sind wie Las Vegas-Algorithmen.

Ich habe kürzlich erfahren, dass es keine bekannte Trennung zwischen den beiden Komplexitäten gibt. Die neueste Referenz, die ich für diese Behauptung finden kann, stammt aus dem Jahr 1998 [1]:

[1] Nikolai K. Vereshchagin, Randomized Boolean Decision Trees: Mehrere Anmerkungen, Theoretical Computer Science, Band 207, Ausgabe 2, 6. November 1998, Seiten 329-342, ISSN 0304-3975, http://dx.doi.org/ 10.1016 / S0304-3975 (98) 00071-1 .

Die bekannteste Obergrenze des einen in Bezug auf das andere ist

R0(f)=Ö(R2(f)2LogR2(f))

aufgrund von [2]:

[2] Kulkarni, R. & Tal, A. (2013, November). Ein Bruchblockempfindlichkeit. In Electronic Colloquium on Computational Complexity (ECCC) (Vol. 20, S. 168).

Ich habe zwei spezifische Fragen.

  1. [Referenzanfrage]: Gibt es eine neuere Veröffentlichung (nach 1998), die dieses Problem behandelt?
  2. Noch wichtiger ist , gibt es eine Kandidatenfunktion, von der vermutet wird, dass sie diese beiden Komplexitäten trennt?

Hinzugefügt in v2: Hinzugefügt in ref [2], betonte die zweite Frage nach der Existenz der Kandidatenfunktion.

Robin Kothari
quelle

Antworten:

7

Soweit ich weiß, ist dies noch offen. Ein neueres Papier, das diese Größen und einige Grenzen erwähnt, ist Aaronson et al .: Schwache Parität (siehe http://arxiv.org/abs/1312.0036 ). Sie können auch Kapitel 14 von Jukna: Boolesche Funktionen und die Umfrage von 1999 (noch besser als 1998!) Von Buhrman und de Wolf sehen. Magniez et al .: http://arxiv.org/abs/1309.7565

Zum Schluss noch eine kurze Zusammenfassung, die ich letzten Monat für mich gemacht habe (ohne Defs):

R2 <= R0 <= D <= n

D <= N0 * N1 <= C ^ 2 <= R0 ^ 2

s <= bs <= C <= s * bs <= bs ^ 2 (neu: [Gilmer-Saks-Srinivasan]: es gibt f st bs ^ 2 (f) = O (C (f))

D <= N1 * bs <= bs ^ 3 <= (3R2) ^ 3

deg <= D <= bs * deg <= deg ^ 3 (neu: [Tal]: bs <= deg ^ 2)

D <= N1 * deg

C <= bs * deg 2 <= deg 4

Die Sensitivitätsvermutung besagt, dass s auch polynomiell mit anderen Parametern zusammenhängt.

domotorp
quelle
Können Sie konkret darauf hinweisen, wo diese Arbeiten die Frage von Las Vegas vs. Monte Carlo-Algorithmen behandeln? Ich habe versucht, es in diesen Zeitungen zu suchen, konnte es aber nicht finden.
Robin Kothari
Es tut mir leid, wenn ich mehrdeutig war, diese Papiere erwähnen die Frage nicht explizit, nur unterschiedliche Ungleichungen für die verschiedenen Parameter. Mein einziger Beweis für die Offenheit der Frage ist, dass, wenn es nicht so wäre, es erwähnt würde.
Domotorp
Oh, ich verstehe was du meinst. Ich habe diese Papiere gelesen. Ich frage mich, ob dieses Problem in jüngerer Zeit genauer untersucht wurde. Und ich bin auch neugierig, ob es eine Funktion gibt, die diese beiden Komplexitäten trennen könnte. (Oder wenn die Leute glauben, dass sie gleich sind.)
Robin Kothari
Ich weiß, dass vermutet wird, dass die größte Trennung von D der NAND-Baum für R0 und R2 ist.
Domotorp
7

Diese Frage wurde gelöst!

f

R0(f)=Ω~(R2(f)2)

und sogar

R0(f)=Ω~(R1(f)2)

R1(f)

Beide Abstände sind bis auf logarithmische Faktoren optimal!

Robin Kothari
quelle
In der neuen Version ihres Papiers wurde dies auf eine nahezu quadratische Lücke verbessert, die logarithmisch eng ist.
Shalev