Setiap algoritma acak dapat disimulasikan oleh algoritma deterministik, dengan mengorbankan peningkatan eksponensial dalam waktu berjalan. Derandomisasi adalah tentang mengubah algoritma acak menjadi algoritma deterministik yang efisien.
Sebuah pertanyaan baru - baru ini oleh Huck Bennett yang menanyakan apakah kelas PH terkandung dalam kelas PP, menerima jawaban yang agak kontradiktif (sepertinya benar). Di satu sisi, beberapa hasil oracle diberikan sebaliknya, dan di sisi lain Scott menyarankan bahwa jawabannya kemungkinan...
Dugaan bahwa keacakan tidak memperpanjang kekuatan algoritma waktu polinomial, yaitu, diperkirakan untuk ditahan. Di sisi lain, keacakan tampaknya memiliki efek yang sangat berbeda pada pengurangan waktu polinomial . Dengan hasil Valiant dan Vazirani yang terkenal, berkurang menjadi melalui...
Saya sering mendengar bahwa untuk banyak masalah kita tahu algoritma acak yang sangat elegan, tetapi tidak ada, atau hanya, solusi deterministik yang lebih rumit. Namun, saya hanya tahu beberapa contoh untuk ini. Paling menonjol Quicksort acak (dan algoritma geometris terkait, misalnya untuk...
The Valiant-Vazirani teorema mengatakan bahwa jika ada algoritma waktu polinomial (deterministik atau acak) untuk membedakan antara formula SAT yang memiliki tepat satu tugas memuaskan, dan formula unsatisfiable - maka NP = RP . Teorema ini dibuktikan dengan menunjukkan bahwa UNIQUE-SAT adalah NP...
Dalam satu kalimat: apakah akan ada hierarki untuk menyiratkan hasil derandomisasi?BPTIMEBPTIME\mathsf{BPTIME} Pertanyaan yang terkait tetapi tidak jelas adalah: apakah keberadaan hierarki untuk menyiratkan adanya batas bawah yang sulit? Apakah resolusi masalah ini menabrak penghalang yang dikenal...
Masalah apa yang diketahui milik tetapi tidak diketahui milik ?PBPPBPP\mathsf{BPP}PP\mathsf P Lebih tepatnya, saya tertarik pada masalah independen , yaitu derandomisasi yang tidak diketahui setara. Misalnya, diketahui bahwa deritimasi PIT dan faktorisasi polinomial multivariat adalah sama dan...
RP adalah kelas masalah yang dapat diputuskan oleh mesin Turing nondeterministik yang berakhir dalam waktu polinomial, tetapi itu juga memungkinkan kesalahan satu sisi. P adalah kelas masalah yang biasa diputuskan oleh mesin Turing deterministik yang berakhir dalam waktu polinomial. P = RP...
Saya mencari ekspander yang tidak seimbang yang "baik" dan "hemat ruang". Secara khusus, grafik reguler-kiri bipartit , , , dengan derajat kiri adalah ekspander -pengembang jika untuk setiap ukuran paling banyak , jumlah tetangga di setidaknya. Diketahui bahwa metode probabilistik menghasilkan...
Apakah ada survei yang baik yang membandingkan berbagai ekstraktor, konsentrator dan superconcentrator dan menjabarkan metode terbaik dalam hal tradeoff antara keacakan, waktu dan ruang?
Dengan beberapa algoritma acak Anda dapat derandomisasi algoritma, menghilangkan (dengan biaya yang mungkin dalam waktu berjalan) penggunaan bit acak dan memaksimalkan beberapa batas bawah pada tujuan (biasanya dihitung menggunakan fakta bahwa teorema adalah tentang kinerja yang diharapkan dari...
Sementara teorema Adleman menunjukkan, bahwa , saya tidak mengetahui adanya literatur yang menyelidiki kemungkinan dimasukkannya . Apa konsekuensi kompleksitas-teoretis yang akan dimiliki oleh inklusi seperti itu?BPP⊆P/polyBPP⊆P/poly\mathsf{BPP} \subseteq
Pertimbangkan model berikut: string n-bit r = r 1 ... r n dipilih secara seragam secara acak. Selanjutnya, setiap indeks i∈ {1, ..., n} dimasukkan ke dalam himpunan A dengan probabilitas independen 1/2. Akhirnya, musuh diperbolehkan, untuk setiap i∈A secara terpisah, untuk sandal r i jika...
Misalkan adalah kelas dari masalah keputusan yang memiliki algoritma acak kesalahan dua sisi terikat yang berjalan dalam waktu O ( f ( n ) ) .BPTIME(f(n))BPTIME(f(n))\mathsf{BPTIME}(f(n))O(f(n))O(f(n))O(f(n)) Apakah kita tahu ada masalah sedemikian sehingga Q ∈ B P T I M E ( n k ) tetapi Q ∉ D T I...
Saya tertarik dengan fungsi Boolean eksplisit f:0,1n→0,1f:0,1n→0,1f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}dengan properti berikut: jika fff konstan pada beberapa subruang affine dari0,1n0,1n\\{0,1\\}^n , maka dimensi dari subruang ini adalaho(n)o(n)o(n) . Tidak sulit untuk menunjukkan bahwa...
Distribusi dikatakan ϵ -membodoh fungsi f jika | E x ∈ U ( f ( x ) ) - E x ∈ D ( f ( x ) ) | ≤ ϵ . Dan dikatakan menipu kelas fungsi jika menipu setiap fungsi di kelas itu. Hal ini diketahui bahwa ε ruang -biased menipu kelas paritas lebih himpunan bagian. (lihat
Saya menemukan buku Pairwise Independence and Derandomization pada subjek, tetapi lebih berorientasi pada penelitian daripada berorientasi pada tutorial. Saya baru mengenal subjek "Derandomisasi," dan karena itu, saya ingin tahu referensi mana yang harus dimulai? Saya lebih suka yang membahas...
Nisan membuktikan dalam "Psuedorandom Generator untuk Space-Bounded Computation", bahwa ada generator pseudo-acak yang "membodohi" perhitungan yang dibatasi ruang. Apakah konstruksi ini berlaku untuk setiap oracle (setidaknya untuk permintaan
Kami tahu (untuk saat ini sekitar 40 tahun, terima Adleman, Bennet dan Gill) bahwa masuknya BPP P / poli, dan bahkan lebih kuat BPP / poli P / poli ditahan. "/ Poli" berarti bahwa kita bekerja secara tidak seragam (sirkuit terpisah untuk setiap panjang input ), sementara P tanpa "/ poli" ini...
Adleman, FOCS'78 menunjukkan bahwa setiap rangkaian acak untuk input dengan panjang dapat tidak dereragamkan. Namun, konstruksi secara efektif menduplikasi sirkuit asli O ( n ) kali, sehingga sirkuit derandomisasi lebih besar dari yang asli dengan faktor O ( n ) . Apakah ada konstruksi yang lebih...
Apa saja contoh utama derandomisasi yang sukses atau setidaknya kemajuan dalam menunjukkan bukti konkret terhadap tujuan (bukan koneksi keacakan kekerasan)?P=BPPP=BPPP=BPP Satu-satunya contoh yang terlintas di pikiran saya adalah pengujian primitas waktu polinomial deterministik AKS (bahkan untuk...