Las Vegas gegen Monte Carlo randomisierte Entscheidungsbaumkomplexität

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\to \{0,1\}$$f$$D(f)$$x\in\{0,1\}^n$$f(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.)$f$$R_0(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).$f$$R_2(f)$$f(x)$$2/3$

Frage

Was ist über die Frage bekannt, ob

?$R_0(f) = \Theta(R_2(f))$

Es ist bekannt, dass

$R_0(f) = \Omega(R_2(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

$R_0(f) = O(R_2(f)^2 \log{R_2(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.

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.

Diese Frage wurde gelöst!

$f$

$R_0(f) = \tilde{\Omega}(R_2(f)^{2})$

und sogar

$R_0(f) = \tilde{\Omega}(R_1(f)^{2})$

$R_1(f)$

Beide Abstände sind bis auf logarithmische Faktoren optimal!