Apa simulasi BPP yang paling cepat diketahui menggunakan algoritma Las Vegas?

$\mathsf{BPP}$ dan $\mathsf{ZPP}$ adalah dua kelas kompleksitas probabilistik dasar.

$\mathsf{BPP}$ adalah kelas bahasa yang diputuskan oleh algoritma Turing polinomial-waktu probabilistik di mana probabilitas algoritma mengembalikan jawaban yang salah dibatasi, yaitu probabilitas kesalahan paling banyak $\frac{1}{3}$ (untuk instance YA dan TIDAK).

Di sisi lain, $\mathsf{ZPP}$ algoritma dapat dilihat sebagai orang algoritma probabilistik yang tidak pernah kembali jawaban yang salah, setiap kali mereka kembali jawaban itu benar. Namun waktu berjalan mereka tidak dibatasi oleh polinomial, mereka berjalan dalam polinomial yang diharapkan.

Misalkan $\mathsf{ZPTime}(f)$ menjadi kelas bahasa diputuskan oleh algoritma probabilistik dengan probabilitas nol kesalahan dan diharapkan berjalan-waktu $f$ . Ini juga disebut sebagai algoritma Las Vegas dan $\mathsf{ZPP} = \mathsf{ZPTime}(n^{O(1)})$ .

Pertanyaan saya adalah apa yang paling tahu simulasi algoritma $\mathsf{BPP}$ menggunakan algoritma Las Vegas? Bisakah kita mensimulasikan mereka dalam waktu yang diharapkan subeksponensial? Apakah ada perbaikan yang diketahui dari simulasi brute-force sepele yang membutuhkan waktu eksponensial?

Lebih formal, apakah kita tahu jika $\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{O(n^{\epsilon})})$ atau $\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{n-n^{\epsilon}})$ untuk beberapa $\epsilon>0$ ?

cc.complexity-theory complexity-classes randomness randomized-algorithms sungguh-sungguh
sumber

Berapakah n, panjang input? Mengapa kami dapat menerima dalam

2^{n}

$2^n$

domotorp

adalah hal yang sama dengan

2^{p o l y (n) - n^{ϵ}}

$2^{\mathrm{poly}(n)-n^\epsilon}$

2^{p o l y (n)}

$2^{\mathrm{poly}(n)}$

Emil Jeřábek

Saya menemukan pertanyaan yang cukup menarik. Saya mengedit pertanyaan untuk membuatnya lebih mudah dibaca dan tepat. Silakan mengedit lebih lanjut. ps: Saya menduga bahwa Anda mungkin ingin mempertimbangkan banyak bit acak polinomi yang digunakan oleh algoritma BPP sebagai parameter untuk waktu simulasi tetapi sebagai Emil menunjukkan apa yang Anda tulis memberikan

. Jika Anda ingin, Anda harus mengganti BPP dengan kelas khusus algoritma kesalahan probabilistik terbatas yang memiliki parameter untuk jumlah bit acak yang digunakan oleh algoritma.

2^{p o l y (n)}

$2^{poly(n)}$

Kaveh

Anda dapat meminta jika kita dapat mensimulasikan algoritma BPP yang menggunakan

bit acak dalam

sejak brute-force simulasi berjalan di

waktu.

r (n)

$r(n)$

Z P T i m e (2^{r (n) - n^{ϵ}} n^{O (1)})

$\mathsf{ZPTime}(2^{r(n)-n^\epsilon}n^{O(1)})$

2^{r (n)} n^{O (1)}

$2^{r(n)}n^{O(1)}$

Kaveh

Jawaban:

Pertama, amati bahwa jika untuk beberapa konstan , maka . (Bukti oleh hierarki waktu nondeterministik.) Jadi membuktikan inklusi semacam itu akan menjadi signifikan, bukan hanya karena ini merupakan simulasi yang ditingkatkan tetapi juga akan menghasilkan kemajuan pertama pada batas waktu acak yang lebih rendah dalam beberapa dekade. $\mathsf{BPP} \subseteq \mathsf{ZPTIME}[2^{n^{c}}]$ $c$ $\mathsf{BPP} \neq \mathsf{NEXP}$

Berikutnya, pertimbangkan kelas $\mathsf{PromiseBPP}$ , yang masalah berikut adalah " -hard": $\mathsf{PromiseBPP}$

Sirkuit Approximation Probabilitas Masalah (CAPP): Mengingat sirkuit , output penerimaan probabilitas untuk dalam faktor aditif. $C$ $C$ $1/6$

Hasil Impagliazzo, Kabanets, dan Wigderson 2002 menyiratkan bahwa waktu algoritma nol-kesalahan untuk CAPP (di mana adalah ukuran ) akan berarti . Dalam STOC'10, saya memperluas ini untuk menunjukkan: seandainya untuk setiap dengan bit input dan ukuran , seseorang dapat menghitung CAPP nondeterministis (jadi, nol-kesalahan mencukupi) dalam $2^{n^{\varepsilon}}$ $n$ $C$ $\mathsf{NEXP} \not\subset \mathsf{P/poly}$ $C$ $k$ $n$ waktu, lalu . Artinya, tentu saja ada masalah yang dapat dikomputasi dengan keacakan kesalahan dua sisi, di mana algoritma zero-error yang bahkan sedikit mengalahkan pencarian lengkap akan menyiratkan batas bawah sirkuit. Saya percaya ini harus ditafsirkan sebagai metode yang mungkin untuk membuktikan batas bawah; jarak tempuh Anda dapat bervariasi. $2^{k-\omega(\log k)}\mathrm{poly}(n)$ $\mathsf{NEXP} \not\subset \mathsf{P/poly}$

Perhatikan bahwa bahkan membuktikan juga terbuka, dan membuktikan bahwa juga akan berarti batas bawah: oleh Kabanets dan Impagliazzo 2004, jika pengujian identitas polinomial (a masalah) adalah dalam untuk semua , maka kita memiliki batas yang lebih rendah untuk Permanen atau $\mathsf{RP} \subseteq \mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ $\mathsf{coRP}$ $\mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ $\varepsilon > 0$ $\mathsf{NEXP}$ . Baru-baru ini (mendatang di STOC'13), saya membuktikan tanpa syarat bahwa atau memiliki sirkuit ukuran , membangun metode "saksi mudah" dari Kabanets. Ini menyiratkan dua hal: $\mathsf{BPP} \subseteq \mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^{\varepsilon}$ $\mathsf{RTIME}[2^n]$ $n^c$

Ada sehingga untuk semua , adalah tanpa syarat di - ini adalah tentang derandomization tanpa syarat terbaik dari di yang kita kenal selama ini. $c$ $\varepsilon > 0$ $\mathsf{RP}$ $\mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^c$ $\mathsf{RP/BPP}$ $\mathsf{ZPP}$
Untuk mulai mendapatkan simulasi subeksponensial yang menarik dari , Anda "hanya" harus mengasumsikan tidak memiliki sirkuit ukuran polinomial tetap. $\mathsf{BPP}$ $\mathsf{RTIME}[2^n]$

Ryan Williams
sumber

Terima kasih kepada Niel yang telah meluangkan waktu untuk membuat jawaban saya dapat terbaca :)

Ryan Williams

Ryan, saya pikir saya akan mengajukan pertanyaan yang sangat bodoh, tetapi ini dia: dalam kalimat pertama Anda, mengapa Anda perlu "untuk semua

"? Bukan BPP subset dari ZPTIME (2 ^ (n ^ c)) untuk beberapa c yang tetap menyiratkan subset BPP dari RTIME (2 ^ (n ^ c)) dan oleh karena itu NTIME (2 ^ (n ^ c)), jadi BPP adalah tidak sama dengan NEXP atau NTIME (2 ^ (2n ^ c))) adalah bagian dari NTIME (2 ^ (n ^ c))?

ϵ

$\epsilon$

Sasho Nikolov

Tidak bodoh sama sekali - memang,

untuk beberapa

sudah cukup untuk

, terima kasih telah menunjukkannya. Algoritma waktu subeksponensial diperlukan untuk konsekuensi lainnya.

B P P \subseteq N T I M E (2^{n^{c}})

$BPP \subseteq NTIME(2^{n^c})$

c

$c$

B P P \neq N E X P

$BPP \neq NEXP$

Ryan Williams

Ryan: Jika saya ingin memahami makalah Anda buku apa / makalah tentang kompleksitas sirkuit yang Anda rekomendasikan untuk Anda kenali?

T ....

Hai Arul, untungnya Bill Gasarch menanyakan pertanyaan ini beberapa waktu lalu, dan memasang laman web tautan berikut: cs.umd.edu/~gasarch/ryan/ryan.html

Ryan Williams

Itu tergantung pada asumsi apa yang ingin Anda buat.

Di bawah asumsi kekerasan tertentu, yaitu , Anda mendapatkan bahwa . Ini secara khusus mengimplikasikan bahwa , dan oleh karena itu setiap bahasa diterima oleh mesin Las Vegas (lihat "P = BPP kecuali E memiliki Sirkuit Sub-Responsif: Melakukan Penguraian Simbol XOR Lemma", oleh Impagliazzo dan Wigderson). $E \not\subseteq SIZE(2^{\varepsilon n})$ $P = BPP$ $BPP = ZPP$ $L \in BPP$

Anda juga dapat membuat asumsi lebih ringan kekerasan, yaitu, bahwa , dan mendapatkan bahwa (lihat Lemma 46 di "Dalam mencari sebuah saksi mudah: waktu eksponensial vs waktu polinomial probabilistik "oleh Impagliazzo, Kabanets dan Wigderson). $ZPE \not\subseteq \rm{io-DTIME}(2^{\varepsilon n})$ $BPP = ZPP$

Atau Meir
sumber

Kecuali ada kemajuan dalam derandomisasi, bagi saya seolah-olah persyaratan bahwa Mesin Las Vegas tidak membuat kesalahan adalah penting, sehingga ada sedikit atau tidak ada manfaat untuk memiliki keacakan sama sekali dalam kasus ini.

Untuk bahasa BPP diputuskan oleh algoritma yang cocok , yang bekerja pada input dan string acak mewakili pilihan acaknya, kriteria zero-error menyiratkan kriteria bahwa mesin Las Vegas harus memastikan dengan pasti mana dari kedua kasus $L$ $A$ $x \in \{0,1\}^n$ $r \in \{0,1\}^{N(n)}$ tahan. Jika kita tidak diberi informasi lebih lanjut tentang, maka ini pada dasarnya adalah masalah janji oracle: diberi oraclekomputasi, dan diberi janji bahwamenghasilkan satu outputuntuk setidaknya dua kali lebih banyak input dibandingkan dengan output, tentukan output mana yang lebih umum.

\underset{r}{Pr} (A accepts (x, r)) ⩾ \frac{2}{3} or \underset{r}{Pr} (A accepts (x, r)) ⩽ \frac{1}{3}

$\Pr_r(\text{$A$ accepts $(x,r)$}) \geqslant \tfrac{2}{3} \quad\text{or}\quad \Pr_r(\text{$A$ accepts $(x,r)$}) \leqslant \tfrac{1}{3}$

A

$A$

A^{'}

$A'$

A^{'} (r) = A (x, r)

$A'(r) = A(x,r)$

A^{'}

$A'$

a \in {0, 1}

$a \in \{0,1\}$

1 - a

$1-a$

Meskipun Mesin Las Vegas dapat menggunakan teknik acak, jika kita memang dipaksa untuk memperlakukan sebagai ramalan, kita dapat melihat bahwa satu-satunya strategi yang tersedia untuk mesin Las Vegas adalah dengan mengambil survei yang relatif menyeluruh (meskipun tidak lengkap) dari string acak , untuk melihat jawaban apa yang diberikan untuk masing-masing. Ini hanya dapat memastikan jika ia menemukan lebih dari $A'$ $r$ string berbeda yang semuanya menghasilkan output yang sama; jika tidak, dengan probabilitas kecil (tetapi tidak nol!), mungkin tidak beruntung dan mendapatkan sampel yang tidak representatif dari kemungkinan keluaran. Untuk mendapatkan kesalahan nol, sampel minimal harus $2^{N(n)}\!/3$ $r$ input . $2^{N(n)}\!/3$ $r$

Karena mesin Las Vegas harus memeriksa setidaknya sebagian kecil konstan semua kemungkinan string acak , asimtotik kita tidak lebih baik daripada jika kita deterministik menguji semua kemungkinan string acak. Kami tidak mendapatkan keuntungan asimtotik dalam mensimulasikan algoritma BPP secara acak dalam pengaturan zero-error, di luar apa yang dapat kita lakukan secara deterministik dengan brute-force. $r$

Perhatikan bahwa argumen yang sama ini menimbulkan pemisahan oracle antara BPP dan ZPP , yaitu ada oracle sehingga karena ZPP algoritma membutuhkan waktu eksponensial, sementara BPP algoritma dapat memecahkan pertanyaan tentang oracle dalam satu permintaan dan berhasil dengan kesalahan yang dibatasi. Namun, itu tidak memberi tahu Anda lebih dari apa yang Anda duga sebelumnya (bahwa overhead simulasi mungkin lebih buruk daripada polinomial) atau bahwa asimptotik sama buruknya dengan simulasi deterministik naif. $A$

{Z P P}^{A} ⫋ {B P P}^{A}

$\mathsf{ZPP}^A \subsetneqq \mathsf{BPP}^A$

Niel de Beaudrap
sumber

koreksi saya jika saya salah: Anda memberikan alasan intuitif mengapa derandomisasi tampaknya tidak mungkin, tetapi kita tahu bahwa di bawah beberapa asumsi yang masuk akal BPP, ZPP, dan P semuanya sama. sehingga intuisi belum tentu baik

Sasho Nikolov

Tidak semuanya. Derandomisasi mungkin akan menjadi wawasan tentang bagaimana mensimulasikan BPP oleh P , bukan? Saya hanya menjelaskan bagaimana, jika dia menginginkan hasil tanpa syarat yang tidak mengeksploitasi struktur algoritma itu sendiri, dia mungkin juga melakukan simulasi deterministik sebagai nol-kesalahan secara acak. Atau ada yang salah dengan penjelasan ini?

Niel de Beaudrap

saya pikir semua yang Anda katakan adalah bahwa simulasi brute force naif BPP oleh ZPP tidak jauh lebih cepat daripada simulasi brute force naif BPP oleh P. tetapi saya tidak bisa melihat apa yang seharusnya ditampilkan. bagi saya ini seperti seseorang bertanya 'apa algoritma tercepat untuk menemukan pencocokan maksimum' dan mendapatkan sebagai jawaban 'baik, gagal wawasan tentang struktur pencocokan, saatnya eksponensial'. pertanyaannya adalah bertanya apakah ada beberapa wawasan yang diketahui tentang struktur BPP yang memungkinkan simulasi ZPP efisien

Sasho Nikolov

@SashoNikolov: Itu tidak dimaksudkan untuk menjadi wawasan yang mendalam. Dari kata-kata dalam pertanyaan, bagi saya sepertinya merupakan batas untuk bermigrasi ke CS.SE. Saya memutuskan untuk menjawabnya secara harfiah, yaitu: sejauh yang kami tahu , waktu yang diharapkan paling efisien dari Las Vegas Machine yang menerima bahasa L∈BPP tidak jauh lebih baik daripada mesin deterministik yang mengeksplorasi kemungkinan kekerasan. Jawaban yang mengatakan bahwa itu mungkin menjadi beberapa polinomial atas terikat jika beberapa kondisi memegang sangat baik dan informatif, dan saya memilih mereka untuk itu; tapi saya menjawab pertanyaan yang sebenarnya.

Niel de Beaudrap

Saya pikir ini adalah jawaban yang bagus (juga lebih mudah dibaca setelah diedit). Kami tidak memiliki hasil kondisional seperti "P = ZPP menyiratkan P = BPP" atau "ZPP = BPP menyiratkan P = BPP" sehingga masih mungkin bahwa kami dapat mensimulasikan BPP dengan algoritma ZP lebih cepat daripada dengan algoritma deterministik. Namun hasil relativization tampaknya menyiratkan bahwa ini tidak dapat terjadi dengan simulasi relativizing, apakah saya mengerti dengan benar?

Kaveh