Las Vegas vs Monte Carlo losowa złożoność drzew decyzyjnych

Tło:

Złożoność drzewa decyzyjnego lub złożoność zapytań to prosty model obliczeń zdefiniowany w następujący sposób. Niech będzie funkcją logiczną. Deterministyczna złożoność zapytania f , oznaczona jako D ( f ) , jest minimalną liczbą bitów wejścia x ∈ { 0 , 1 } n, które należy odczytać (w najgorszym przypadku) za pomocą algorytmu deterministycznego obliczającego f ( x $f:\{0,1\}^n\to \{0,1\}$$f$$D(f)$$x\in\{0,1\}^n$$f(x)$. Zauważ, że miarą złożoności jest liczba odczytanych bitów danych wejściowych; wszystkie inne obliczenia są bezpłatne.

Podobnie, definiujemy losową złożoność kwerendy w Las Vegas , oznaczoną R 0 ( f ) , jako minimalną liczbę bitów wejściowych, które należy odczytać w oczekiwaniu przez algorytm losowy o zerowym błędzie, który oblicza f ( x ) . Algorytm o zerowym błędzie zawsze wyświetla poprawną odpowiedź, ale liczba odczytanych przez niego bitów zależy od wewnętrznej losowości algorytmu. (Dlatego mierzymy oczekiwaną liczbę odczytanych bitów wejściowych).$f$$R_0(f)$$f(x)$

Zdefiniować Monte Carlo losowo zapytania złożoność , oznaczoną R 2 ( f ) , aby być minimalna liczba bitów wejściowych, które muszą być odczytywane za pomocą ograniczonego błędu-randomizowane algorytm, który oblicza f ( x ) . Algorytm ograniczony błędów zawsze generuje odpowiedź na końcu, ale to dopiero musi być prawidłowa z prawdopodobieństwem większym niż 2 / 3 (powiedzmy).$f$$R_2(f)$$f(x)$$2/3$

Pytanie

Co wiadomo na pytanie, czy

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

Wiadomo, że

$R_0(f) = \Omega(R_2(f))$

ponieważ algorytmy Monte Carlo są co najmniej tak samo skuteczne jak algorytmy Las Vegas.

Niedawno dowiedziałem się, że nie ma znanego podziału między tymi dwoma złożonościami. Najnowsze odniesienie, które mogę znaleźć dla tego roszczenia, pochodzi z 1998 r. [1]:

[1] Nikolai K. Vereshchagin, Randomizowane logiczne drzewa decyzyjne: kilka uwag, Theoretical Computer Science, tom 207, wydanie 2, 6 listopada 1998, strony 329-342, ISSN 0304-3975, http://dx.doi.org/ 10.1016 / S0304-3975 (98) 00071-1 .

Najbardziej znaną górną granicą jednego pod względem drugiego jest

$R_0(f) = O(R_2(f)^2 \log{R_2(f)})$

z powodu [2]:

[2] Kulkarni, R., i Tal, A. (2013, listopad). Czułość bloku ułamkowego. W Electronic Colloquium on Computational Complexity (ECCC) (Vol. 20, s. 168).

Mam dwa konkretne pytania.

1. [Wniosek o referencję]: Czy istnieje nowszy artykuł (po 1998 r.), Który omawia ten problem?
2. Co ważniejsze , czy istnieje funkcja kandydata, która jest przypuszczana w celu oddzielenia tych dwóch zawiłości?

Dodano w v2: Dodano odniesienie [2], podkreślono drugie pytanie o istnieniu funkcji kandydującej.

O ile mi wiadomo, jest to nadal otwarte. Bardzo niedawny artykuł, w którym wspomniano o tych ilościach i niektórych granicach, to Aaronson i in .: Słaba parzystość (patrz http://arxiv.org/abs/1312.0036 ). Możesz także zobaczyć rozdział 14 Jukna: Funkcje boolowskie i ankietę 1999 (wciąż bije 1998!) Buhrmana i de Wolfa. Kolejny bardzo niedawny artykuł na temat złożoności losowych drzew decyzyjnych to Magniez i in .: http://arxiv.org/abs/1309.7565

Wreszcie krótkie podsumowanie, które zrobiłem dla siebie w zeszłym miesiącu (bez defs):

R2 <= R0 <= D <= n

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

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

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

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

D <= N1 * deg

C <= bs * deg ^ 2 <= deg ^ 4

Hipoteza wrażliwości polega na tym, że s jest również wielomianowo powiązany z innymi parametrami.

To pytanie zostało rozwiązane!

$f$

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

i nawet

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

$R_1(f)$

Oba separacje są optymalne do współczynników log!