Las Vegas vs Monte Carlo secara acak kompleksitas pohon keputusan

Latar Belakang:

Kompleksitas pohon keputusan atau kompleksitas kueri adalah model perhitungan sederhana yang didefinisikan sebagai berikut. Biarkan menjadi fungsi Boolean. Kompleksitas kueri deterministik dari f , dilambangkan D ( f ) , adalah jumlah bit minimum dari input x ∈ { 0 , 1 } n yang perlu dibaca (dalam kasus yang lebih buruk) oleh algoritma deterministik yang menghitung f ( x $f:\{0,1\}^n\to \{0,1\}$$f$$D(f)$$x\in\{0,1\}^n$$f(x)$. Perhatikan bahwa ukuran kompleksitas adalah jumlah bit dari input yang dibaca; semua perhitungan lainnya gratis.

Demikian pula, kami mendefinisikan kompleksitas kueri acak Las Vegas dari , yang dilambangkan R 0 ( f ) , sebagai jumlah minimum bit input yang perlu dibaca dengan harapan dengan algoritma acak nol-kesalahan yang menghitung f ( x ) . Algoritma zero-error selalu menghasilkan jawaban yang benar, tetapi jumlah bit input yang dibacanya tergantung pada keacakan internal algoritma. (Inilah sebabnya kami mengukur jumlah bit input yang diharapkan.)$f$$R_0(f)$$f(x)$

Kami mendefinisikan kompleksitas kueri acak Monte Carlo dari , dilambangkan R 2 ( f ) , menjadi jumlah bit input minimum yang perlu dibaca oleh algoritma acak terbatas-galat yang menghitung f ( x ) . Algoritma dibatasi-kesalahan selalu output jawaban di akhir, tapi hanya perlu benar dengan probabilitas lebih besar dari 2 / 3 (katakanlah).$f$$R_2(f)$$f(x)$$2/3$

Pertanyaan

Apa yang diketahui tentang pertanyaan apakah

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

Diketahui bahwa

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

karena algoritma Monte Carlo setidaknya sama kuatnya dengan algoritma Las Vegas.

Baru-baru ini saya mengetahui bahwa tidak ada pemisahan yang diketahui antara kedua kompleksitas. Referensi terbaru yang dapat saya temukan untuk klaim ini adalah dari tahun 1998 [1]:

[1] Nikolai K. Vereshchagin, pohon keputusan Boolean Acak: Beberapa komentar, Ilmu Komputer Teoritis, Volume 207, Edisi 2, 6 November 1998, Halaman 329-342, ISSN 0304-3975, http://dx.doi.org/ 10.1016 / S0304-3975 (98) 00071-1 .

Batas atas yang paling dikenal dari satu dalam hal yang lain adalah

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

karena [2]:

[2] Kulkarni, R., & Tal, A. (2013, November). Pada Sensitivitas Blok Pecahan. Dalam Kolokium Elektronik tentang Kompleksitas Komputasi (ECCC) (Vol. 20, p. 168).

Saya punya dua pertanyaan spesifik.

1. [Permintaan referensi]: Apakah ada makalah yang lebih baru (setelah 1998) yang membahas masalah ini?
2. Lebih penting lagi , adakah fungsi kandidat yang diperkirakan untuk memisahkan kedua kompleksitas ini?

Ditambahkan dalam v2: Added ref [2], menekankan pertanyaan kedua tentang keberadaan fungsi kandidat.

Sejauh yang saya tahu, ini masih terbuka. Makalah yang sangat baru yang menyebutkan jumlah ini dan beberapa batasan adalah Aaronson et al: Paritas lemah (lihat http://arxiv.org/abs/1312.0036 ). Anda juga dapat melihat bab 14 Jukna: fungsi Boolean dan survei 1999 (masih berdetak 1998!) Oleh Buhrman dan de Wolf. Makalah yang sangat baru tentang kompleksitas pohon keputusan acak adalah Magniez et al: http://arxiv.org/abs/1309.7565

Akhirnya, ringkasan singkat yang saya buat untuk diri saya sendiri bulan lalu (tanpa def):

R2 <= R0 <= D <= n

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

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

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

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

D <= N1 * deg

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

Dugaan sensitivitas adalah bahwa s juga berhubungan secara polinomi dengan parameter lain.

Pertanyaan ini telah diselesaikan!

$f$

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

dan bahkan

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

$R_1(f)$

Kedua pemisahan optimal hingga faktor log!