Kapan pengacakan mempercepat algoritma dan "tidak seharusnya"?

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 [algoritma menjalankan algoritma acak pada Θ ( n $BPP$$P/poly$$t(n)$$n$$\Theta(t(n)\cdot n)$$n$$\Theta(n)$string keacakan independen. Harus ada keacakan untuk algoritma berulang yang baik untuk semua input yang mungkin]. Algoritma deterministik tidak seragam - mungkin berperilaku berbeda untuk ukuran input yang berbeda. Jadi argumen Adleman menunjukkan bahwa - jika seseorang tidak peduli tentang keseragaman - pengacakan hanya dapat mempercepat algoritma dengan faktor yang linier dalam ukuran input.$2^n$

Apa saja contoh konkret di mana pengacakan mempercepat perhitungan (sejauh yang kami ketahui)?

Salah satu contoh adalah pengujian identitas polinomial. Di sini input adalah sirkuit aritmatika n-ukuran yang menghitung polinomial variate-m di atas bidang, dan tugasnya adalah untuk mengetahui apakah polinomialnya identik dengan nol. Algoritma acak dapat mengevaluasi polinomial pada titik acak, sedangkan algoritma deterministik terbaik yang kita tahu (dan mungkin yang terbaik yang ada) mengevaluasi polinomial pada banyak titik.

Contoh lain adalah minimum spanning tree, di mana algoritma acak terbaik oleh Karger-Klein-Tarjan adalah waktu linear (dan probabilitas kesalahan secara eksponensial kecil!), Sedangkan algoritma deterministik terbaik oleh Chazelle berjalan dalam waktu ( α adalah fungsi Ackermann terbalik, jadi percepatan pengacakan sangat kecil). Menariknya, dibuktikan oleh Pettie dan Ramachandran bahwa jika ada algoritma waktu linear deterministik yang tidak seragam untuk pohon rentang minimum, maka ada juga algoritma waktu linear deterministik seragam.$O(m\alpha(m,n))$$\alpha$

Apa saja contoh lainnya? Contoh mana yang Anda tahu di mana kecepatan pengacakan besar, tetapi ini mungkin hanya karena kami belum menemukan algoritma deterministik yang cukup efisien?

Saya tidak tahu apakah pengacakan “harus” atau “tidak seharusnya” membantu, namun, pengujian bilangan bulat integer dapat dilakukan dalam waktu menggunakan pengacakan Miller-Rabin, sementara sejauh yang saya tahu, yang paling terkenal algoritma deterministik adalah ˜ O ( n 4 ) dengan asumsi GRH (deterministik Miller-Rabin) atau ˜ O ( n 6 ) tanpa syarat (varian AKS).$\tilde O(n^2)$$\tilde O(n^4)$$\tilde O(n^6)$

Contoh lama adalah perhitungan volume. Diberikan polytope yang dijelaskan oleh oracle keanggotaan, ada algoritma acak yang berjalan dalam waktu polinomial untuk memperkirakan volumenya menjadi faktor , tetapi tidak ada algoritma deterministik yang dapat mendekati bahkan tanpa syarat .$1+\epsilon$

Contoh pertama dari strategi acak semacam itu adalah oleh Dyer, Frieze dan Kannan, dan hasil kekerasan untuk algoritma deterministik adalah oleh Bárány dan Füredi. Alistair Sinclair memiliki catatan kuliah yang bagus tentang ini .

Saya tidak yakin saya sepenuhnya memahami bagian "dan seharusnya tidak" dari pertanyaan, jadi saya tidak yakin ini sesuai dengan tagihan.

saya tidak tahu apakah ini menjawab pertanyaan Anda (atau setidaknya sebagian dari itu). Tetapi untuk contoh dunia nyata di mana pengacakan dapat memberikan percepatan adalah masalah optimasi dan hubungannya dengan teorema No Free Lunch ( NFL ) .

Ada sebuah makalah "Mungkin bukan makan siang gratis tapi setidaknya pembuka gratis" di mana ditunjukkan bahwa menggunakan pengacakan, algoritma (optimasi) dapat memiliki kinerja yang lebih baik.

Abstrak:

$f : X \rightarrow Y$$X$$Y$adalah set terbatas. Hasil ini disebut Theorem No Lunch Gratis. Di sini disajikan berbagai skenario optimasi. Dikatakan mengapa skenario di mana Teorema No Free Lunch didasarkan tidak memodelkan optimasi kehidupan nyata. Untuk skenario yang lebih realistis dikatakan mengapa teknik optimasi berbeda dalam efisiensinya. Sebagai contoh kecil, klaim ini terbukti.

Referensi:

1. Tidak Ada Teorema Makan Siang Gratis untuk Optimasi ( teorema NFL asli untuk optimisasi)
2. Mungkin bukan makan siang gratis tapi setidaknya makanan pembuka gratis
3. $F$$F$
4. Pada kelas fungsi yang tidak mengandung hasil Makan Siang Gratis (Terbukti bahwa sebagian kecil dari himpunan bagian cangkir adalah sangat kecil)
5. Dua Kelas Fungsi Luas yang Tidak Ada Hasil Makan Siang Gratis Tidak Tahan (menunjukkan bahwa hasil NFL tidak berlaku untuk serangkaian fungsi ketika panjang deskripsi fungsi dibatasi dengan cukup)
6. Makan siang berkelanjutan gratis plus desain algoritma optimalisasi optimal (menunjukkan bahwa untuk domain berkelanjutan, [versi resmi] NFL tidak berlaku. Teorema makan siang gratis ini didasarkan pada formalisasi konsep fungsi kebugaran acak dengan cara bidang acak) )
7. Melampaui Tanpa Makan Siang Gratis: Algoritma Realistis untuk Kelas Masalah Sewenang-wenang (menunjukkan bahwa ".. [a] akan pelanggaran teorema Tanpa Makan Siang Gratis dapat dinyatakan sebagai distribusi non-blok-seragam atas subset masalah yang merupakan cawan ")
8. Algoritma Metaheuristik Berbasis Kawanan dan Teorema Tanpa Makan Siang ("[..t] di sini, hasil untuk iterasi yang tidak ditinjau berdasarkan waktu mungkin tidak berlaku untuk kasus yang meninjau kembali kasus, karena iterasi yang meninjau kembali melanggar asumsi penting dari cup diperlukan untuk membuktikan teorema NFL (Marshall dan Hinton, 2010) ")
9. Tidak Ada Makan Siang Gratis dan Keacakan Algoritma
10. Tidak Ada Makan Siang dan Tolak Ukur Gratis (pendekatan set-teoretis yang digeneralisasikan ke kriteria yang tidak spesifik untuk cangkir , tetapi masih mencatat bahwa algoritma acak (non-sepele) dapat mengungguli algoritma deterministik rata-rata, "[..] telah dibuktikan bahwa probabilitas tidak memadai untuk menegaskan hasil NFL yang tidak terkendala dalam kasus umum. [..] makalah ini mengabaikan probabilitas, lebih memilih kerangka teori-set yang menyingkirkan batasan teori-ukuran dengan membuang probabilitas sama sekali ")

Ringkasan tentang makan siang tanpa-bebas (dan makan siang gratis) oleh David H. Wolpert, Berapa biaya makan malam? ( perhatikan bahwa teorema tipe NFL tidak pernah menentukan " harga " yang sebenarnya karena jenis pembuktiannya)

khusus untuk optimasi umum (GO):

1. $X$$Z$$X$$Z$

2. $f: X \to Z$

3. $m$$f$

   $$d_m = \{d_m(1), d_m(2), ..., d_m(m)\}$$ $\forall t$ $$d_m(t) =\{d^X_m(t),d^Z_m(t)\}$$ $d^Z_m(t)$$f[d^X_m(t)]$

4. $a = \{d_t \to d^X_m(t) : t=0..m\}$

5. $C(f, d_m)$

6. $C(., .)$

$C$$f$$C$$f$$C$$(f, d_m)$$f = f^*$

Akhirnya, sebuah pernyataan sederhana (dan yang tidak terlalu sederhana) mengapa pengacakan (dalam satu bentuk atau lainnya) dapat memberikan kinerja yang unggul daripada algoritma deterministik ketat.

1. Dalam konteks optimisasi (walaupun tidak dibatasi dalam hal ini), prosedur pencarian acak dapat rata-rata keluar dari ekstrem lokal lebih baik daripada pencarian deterministik, dan mencapai ekstrem global.
2. $2^A$$A$$A$$A$$A$

Contoh terbaik adalah di daerah yang dianggap sebagai kandidat terbaik untuk OWFs di mana tampaknya setiap OWF populer yang dimasak secara mengejutkan memiliki algoritma sub-eksponensial acak sementara tidak ada algoritma sub-eksponensial deterministik (ambil faktorisasi integer misalnya). Bahkan, dalam banyak kasus, mungkin ada algoritma yang efisien diberikan beberapa saran string (cryptoanalysis).

Jika Anda memiliki algoritma menggunakan pengacakan, Anda selalu dapat menggantinya dengan algoritma deterministik menggunakan angka pseudo-acak: Ambil deskripsi masalahnya, hitung kode hash, gunakan kode hash itu sebagai seed untuk generator nomor pseudo-acak yang baik . Dalam praktiknya, itulah yang sebenarnya mungkin terjadi ketika seseorang mengimplementasikan algoritma menggunakan pengacakan.

Jika kita meninggalkan kode hash, maka perbedaan antara algoritma ini dan algoritma menggunakan pengacakan yang benar adalah bahwa saya dapat memprediksi urutan angka acak yang dihasilkan, dan saya bisa menghasilkan masalah sehingga prediksi nomor acak yang diterapkan pada masalah saya akan selalu membuat keputusan terburuk. Sebagai contoh, untuk Quicksort dengan pseudo-random pivot, saya dapat membuat array input di mana pseudo-random pivot akan selalu menemukan nilai terbesar dalam array. Dengan keacakan yang sebenarnya itu tidak mungkin.

Dengan kode hash, akan sangat sulit bagi saya untuk membangun masalah di mana angka pseudo-acak menghasilkan hasil terburuk. Saya masih dapat memprediksi angka acak, tetapi jika saya mengubah masalahnya, urutan angka pseudo-acak berubah sepenuhnya. Namun, akan hampir mustahil bagi Anda untuk membuktikan bahwa saya tidak dapat membangun masalah seperti itu.