Contoh derandomisasi yang sukses dari BPP ke P

Apa saja contoh utama derandomisasi yang sukses atau setidaknya kemajuan dalam menunjukkan bukti konkret terhadap tujuan (bukan koneksi keacakan kekerasan)? $P=BPP$

Satu-satunya contoh yang terlintas di pikiran saya adalah pengujian primitas waktu polinomial deterministik AKS (bahkan untuk ini ada metodologi asumsi GRH). Jadi apa bukti spesifik melalui contoh yang kita miliki untuk derandomisasi (sekali lagi bukan kekerasan atau koneksi oracle)?

Harap simpan contoh hanya di mana peningkatan kompleksitas waktu ditunjukkan dari poli acak ke poli deterministik atau sesuatu yang sangat dekat untuk masalah tertentu.

Berikut ini lebih banyak komentar dan saya tidak tahu banyak akan membantu pertanyaan ini.

Chazelle memiliki pernyataan yang sangat menarik di http://www.cs.princeton.edu/~chazelle/linernotes.html di bawah 'Metode Perbedaan: Keacakan dan Kompleksitas (Cambridge University Press, 2000)'.

'Ini merupakan sumber daya tarik yang tiada habisnya bagi saya bahwa pemahaman yang lebih dalam tentang perhitungan deterministik harus membutuhkan penguasaan pengacakan. Saya menulis buku ini untuk menggambarkan hubungan yang kuat ini. Dari pohon spanning minimum ke pemrograman linier ke triangulasi Delaunay, algoritma yang paling efisien sering derandomisasi dari solusi probabilistik. Metode ketidaksesuaian menyoroti salah satu pertanyaan paling bermanfaat dalam semua ilmu komputer: jika Anda pikir Anda membutuhkan bit acak, tolong beri tahu kami mengapa? '

cc.complexity-theory big-list randomized-algorithms derandomization pseudorandom-generators
sumber

Banyak algoritma dapat derandomized menggunakan teknik umum seperti metode ekspektasi bersyarat, metode penduga pesimis, dan menggunakan ruang sampel independensi terikat. Bahkan, pengujian primality dan pengujian identitas polinom sangat terkenal karena mereka adalah contoh langka dari fungsi alami yang menolak teknik derandomisasi standar.

Sasho Nikolov

@SashoNikolov terima kasih mungkin komentarnya dapat diperluas sebagai jawaban lengkap pada beberapa contoh. Juga koneksi kekerasan-keacakan melalui kompleksitas sirkuit satu-satunya alasan orang percaya

P = B P P

$P=BPP$

Saya pikir ini agak terlalu mendasar untuk dijawab. Lihat bab tentang derandomisasi dalam Alon-Spencer untuk detail dan contoh: ini mencakup tiga teknik yang saya sebutkan.

Sasho Nikolov

Hal yang menarik tentang kelas BPP adalah bahwa definisi teoretisnya membutuhkan bit input acak yang dapat dengan mudah ditampilkan, menggunakan de-randomisasi dan ukuran-ukuran acak kolomogrov yang lemah, tidak ada dalam domain terbatas. Saya tidak tahu bagaimana orang bisa hidup dengan ketidakkonsistenan ini. Saya sendiri tidak percaya ada BPP kelas eksplisit (bisa NP atau P).

Jawaban:

. $SL = L$

singkatan logspace acak dan adalah versi lebih kecil dari masalah $RL$ $RL=L$ $RP=P$ . Sebuah batu loncatan besar adalah bukti Reingold di '04 ( "diarahkan ST Konektivitas di logspace") yang , di mana adalah singkatan dari "simetris" dan adalah kelas menengah antara dan . $SL = L$ $S$ $SL$ $RL$ $L$

Idenya adalah bahwa Anda dapat memikirkan mesin Turing logspace acak sebagai grafik diarahkan berukuran polinomial, di mana node adalah keadaan mesin, dan algoritma RL mengambil jalan acak yang memiliki sifat baik. SL sesuai dengan grafik tidak berarah dari formulir ini. Bukti Reingold dibangun berdasarkan kerja pada grafik expander, terutama Reingold, Vadhan, dan "zig-zag" produk Wigderson, untuk mengambil jalan acak pada grafik tidak berarah dengan properti bagus dan mengubahnya menjadi jalan psuedorandom yang mempertahankan properti tersebut.

sunting pertanyaan ini diposting sebelum pertanyaan diubah secara eksplisit untuk fokus secara eksklusif pada P vs BPP ... Saya meninggalkannya karena tampaknya menarik.

usul
sumber

Tolong jangan. Jawabannya menarik.

Emil Jeřábek mendukung Monica

Hai @Student., Saya pikir orang-orang yang datang ke pertanyaan yang tertarik pada contoh derandomisasi yang sukses akan tertarik pada jawaban ini, jadi saya akan menyimpannya, tanpa bermaksud tidak menghargai tujuan Anda (yang kemudian diedit untuk menentukan kompleksitas waktu ... )

usul

Saya juga harus mengatakan bahwa pertanyaan dan jawaban di situs ini seharusnya dirumuskan sehingga umumnya bermanfaat bagi pengunjung masa depan sebagai sumber referensi, tidak hanya sesuai dengan tujuan khusus poster. I untuk satu menemukan pertanyaan tanpa batasan buatan untuk kompleksitas waktu dan BPP jauh lebih berguna.

Emil Jeřábek mendukung Monica

@ EmilJeřábek Ok terima kasih kami akan meninggalkan pos usul seperti di sini.

@ usul 'Idenya adalah Anda dapat menganggap mesin Turing logspace acak sebagai grafik diarahkan berukuran polinomial'. Apakah ada intuisi yang cocok untuk NL? Saya tahu L bukan NL yang diduga tetapi PSPACE = NPSPACE dan karena itu ruang mungkin berbeda dari waktu.

T ....

Pada dasarnya hanya ada satu masalah menarik dalam BPP yang tidak diketahui dalam P: Polynomial Identity Testing, mengingat rangkaian aljabar adalah polinomial yang dihasilkannya identik nol. Impagliazzo dan Kabanets menunjukkan bahwa PIT dalam P akan menyiratkan beberapa batas bawah sirkuit. Jadi batas bawah sirkuit adalah satu-satunya alasan (tapi yang cukup bagus) yang kami percaya P = BPP.

Lance Fortnow
sumber

Sementara saya setuju dengan Anda pada tingkat tinggi, saya pikir bahwa kebanyakan algoritma acak dalam teori grup komputasi menyarankan kelas erat lain pertanyaan dererialisasi menarik, yang tampaknya tidak mengurangi ke PIT. Sementara sebagian besar dari ini adalah fungsi daripada masalah keputusan, beberapa dari mereka dapat disusun

Joshua Grochow

O (f (n))

$O(f(n))$

O (f (n))

$O(f(n))$

B P P

$BPP$

B P P

$BPP$

f (n)

$f(n)$

P = B P P

$P=BPP$

Selain pengujian identitas polinomial, satu masalah lain yang sangat penting diketahui berada di BPP tetapi tidak dalam P adalah mendekati permanen dari matriks non-negatif atau bahkan jumlah kecocokan sempurna dalam grafik. Ada algoritma poli-waktu acak untuk memperkirakan angka-angka ini dalam faktor (1 + eps), sedangkan algoritma deterministik terbaik hanya mencapai ~ 2 ^ n perkiraan faktor.

Sementara permanen adalah contoh utama, ada banyak masalah penghitungan perkiraan yang ada kesenjangan besar antara algoritma acak (biasanya didasarkan pada metode 'MCMC') dan algoritma deterministik.

Masalah lain dalam nada yang sama adalah mendekati volume benda cembung yang diberikan secara eksplisit (katakanlah polihedron yang dijelaskan oleh kumpulan ketidaksetaraan linear).

Raghu Meka
sumber

Satu kehalusan dalam P vs BPP, yang saya harap dapat saya pahami dengan lebih baik, adalah perbedaan antara masalah fungsi dan masalah keputusan. Mungkin ada banyak masalah fungsi yang dapat dipecahkan (dalam beberapa hal) secara acak tetapi tidak secara deterministik dalam waktu polinomial, namun P = BPP. Tampaknya contoh Anda mungkin diterjemahkan dengan mudah ke masalah keputusan, apakah itu benar?

usul

Masalah fungsi vs keputusan sedikit lebih halus daripada di dunia NP, tetapi masih banyak yang diketahui: misalnya makalah ini di bagian 3 memberikan contoh dari "masalah pencarian waktu dipecahkan poli secara acak" yang bahkan tidak dapat diputuskan. Tetapi jika fungsinya satu-ke-satu, maka P = BPP menyiratkan "masalah fungsi waktu terpecahkan poli acak" memiliki algoritme waktu poli deterministik (makalah ini memberikan lebih banyak contoh juga)

Joe Bebel