Algoritma yang perilakunya ditentukan oleh input dan generator yang menghasilkan angka acak seragam.
Bukti Adleman bahwa terkandung dalam P / p o l y menunjukkan bahwa jika ada algoritma acak untuk masalah yang berjalan dalam waktu t ( n ) pada input ukuran n , maka ada juga algoritma deterministik untuk masalah tersebut. yang berjalan dalam waktu Θ ( t ( n ) ⋅ n ) pada input berukuran n...
Banyak yang percaya bahwa . Namun kita hanya tahu bahwa B P P berada pada tingkat kedua hierarki polinomial, yaitu B P P ⊆ Σ P 2 ∩ Π P 2 . Langkah menuju menunjukkan B P P = P adalah untuk pertama membawanya ke tingkat pertama dari hirarki polinomial, yaitu B P P ⊆ N P .BPP=P⊆NPBPP=P⊆NP\mathsf{BPP}...
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...
Apakah ada contoh menarik dari algoritma acak untuk masalah pencarian yang selalu menampilkan jawaban yang sama (benar), terlepas dari keacakan internal, tetapi yang mengeksploitasi keacakan sehingga waktu berjalan yang diharapkan lebih baik daripada waktu berjalan yang paling cepat diketahui...
Log-space-uniform NC terkandung dalam ruang polylog deterministik (kadang-kadang ditulis PolyL). Apakah log-space-uniform RNC juga ada di kelas ini? Versi acak standar dari PolyL harus dalam PolyL, tapi saya tidak melihat bahwa (seragam) RNC berada di dalam Random-PolyL. Kesulitan yang saya lihat...
Saya baru saja mengajarkan algoritma mincut acak Karger-Stein di kelas algoritma lulusan saya. Ini adalah permata algoritmik yang nyata , jadi saya tidak bisa mengajarinya, tetapi selalu membuat saya frustrasi, karena saya tidak tahu aplikasi lain dari teknik utama. (Jadi sulit untuk menetapkan...
Sunting: Saya memilih jawaban dengan skor tertinggi pada 06 Desember 2012. Ini pertanyaan lembut. Konsep algoritma (deterministik) kembali ke SM. Bagaimana dengan algoritma probabilistik? Dalam entri wiki ini , algoritma Rabin untuk masalah pasangan terdekat dalam geometri komputasi diberikan...
Saya yakin semua orang tahu percobaan jarum Buffon di abad ke-18, itu adalah salah satu algoritma probabilistik pertama yang menghitung .ππ\pi Implementasi algoritma di komputer biasanya membutuhkan penggunaan , atau fungsi trigonometrik, yang, bahkan jika mereka diimplementasikan sebagai seri...
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...
Sebuah penting 2003 kertas oleh Childs et al.memperkenalkan "pohon siam masalah": masalah mengakui percepatan kuantum eksponensial yang tidak seperti masalah lain yang kita tahu. Dalam masalah ini, kami diberi grafik besar secara eksponensial seperti yang digambarkan di bawah ini, yang terdiri dari...
Prinsip Minimax Yao yang terkenal menyatakan hubungan antara kompleksitas distribusi dan kompleksitas acak. Biarkan menjadi masalah dengan himpunan berhingga input dan satu set terbatas algoritma deterministik untuk memecahkan . Juga biarkan menunjukkan distribusi input dan biarkan menunjukkan...
Jika adalah fungsi cembung maka ketidaksetaraan Jensen menyatakan bahwa , dan saling mutatis ketika adalah cekung. Jelas dalam kasus terburuk Anda tidak bisa menggunakan batas atas dalam hal untuk cembung , tetapi apakah ada batas yang mengarah ke arah ini jika adalah cembung tetapi "tidak terlalu...
Ketika saya mengajar batas ekor, saya menggunakan progresi yang biasa: Jika rv Anda positif, Anda dapat menerapkan ketimpangan Markov Jika Anda memiliki kemandirian dan juga varian dibatasi, Anda dapat menerapkan ketidaksamaan Chebyshev Jika setiap rv independen juga memiliki semua momen...
Untuk algoritma acak mengambil nilai nyata, "trik median" adalah cara sederhana untuk mengurangi kemungkinan kegagalan pada ambang batas mana pun , dengan biaya hanya pada multiplikatif) overhead. Yaitu, jika output \ mathcal {A} jatuh ke "rentang yang baik" I = [a, b] dengan probabilitas...
Biarkan menjadi fungsi. Kami ingin memperkirakan rata-rata ; yaitu: .f E [ f ( n ) ] = 2 - n ∑ x ∈ { 0 , 1 } n f ( x )f: { 0 , 1 }n→ ( 2- n, 1 ]f:{0,1}n→(2−n,1]f \colon \lbrace 0,1 \rbrace ^ n \to (2^{-n},1]fffE [f( n ) ] = 2- n∑x ∈ { 0 , 1 }nf( x
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...
Satu hal yang dapat dilakukan oleh komputer kuantum (mungkin bahkan hanya dengan sirkuit kuantum log-depth BPP +) adalah untuk memperkirakan-sampel transformasi Fourier dari fungsi Boolean -nilai dalam P.±1±1\pm 1 Di sini dan di bawah ini ketika saya berbicara tentang pengambilan sampel...
Pertanyaan ini terinspirasi oleh t-shirt Georgia Tech Algorithms and Randomness Center , yang menanyakan "Acak atau tidak ?!" Ada banyak contoh di mana pengacakan membantu, terutama ketika beroperasi di lingkungan permusuhan. Ada juga beberapa pengaturan di mana pengacakan tidak membantu atau...
Misalkan saya mempertimbangkan varian BPP berikut, yang kami sebut E (xact) BPP: Suatu bahasa ada di EBPP jika ada waktu polinomial acak TG yang menerima setiap kata dalam bahasa dengan probabilitas 3/4 tepat dan setiap kata tidak dalam bahasa dengan tepat 1/4 probabilitas. Jelas EBPP terkandung...