Algoritma acak yang efisien dan sederhana di mana determinisme sulit

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 cembung cembung)
• Mincut acak
• Pengujian Identitas Polinomial
• Masalah Klee's Measure

Di antaranya, hanya pengujian identitas polinomial yang tampaknya sangat sulit tanpa menggunakan keacakan.

Apakah Anda tahu lebih banyak contoh masalah di mana solusi acak sangat elegan atau sangat efisien, tetapi solusi deterministik tidak? Idealnya, masalahnya harus mudah untuk memotivasi orang awam (tidak seperti misalnya pengujian identitas polinomial).

Menyortir mur dan baut

Masalah berikut ini disarankan oleh Rawlins pada tahun 1992: Misalkan Anda diberi koleksi n mur dan baut n. Setiap baut cocok tepat satu mur, dan jika tidak, mur dan baut memiliki ukuran yang berbeda. Ukurannya terlalu dekat untuk memungkinkan perbandingan langsung antara pasang baut atau pasang mur. Namun, Anda dapat membandingkan mur dengan baut apa pun dengan mencoba mengencangkannya; dalam waktu yang konstan, Anda akan menemukan apakah bautnya terlalu besar, terlalu kecil, atau pas untuk mur. Tugas Anda adalah menemukan baut mana yang cocok dengan masing-masing mur, atau yang setara, untuk mengurutkan mur dan baut berdasarkan ukuran.

Varian langsung quicksort acak memecahkan masalah dalam waktu dengan probabilitas tinggi. Pilih baut acak; menggunakannya untuk mempartisi mur; gunakan mur yang cocok untuk mempartisi baut; dan berulang. Namun, menemukan algoritma deterministik yang bahkan berjalan di o ( n 2 ) adalah nontrivial. Algoritma deterministik O ( n log n ) akhirnya ditemukan pada tahun 1995 oleh Bradford dan secara independen oleh Komlós, Ma, dan Szemerédi. Di bawah tenda, kedua algoritma menggunakan varian dari jaringan sortir paralel AKS, sehingga konstanta tersembunyi di O ( $O(n \log n)$$o(n^2)$$O(n\log n)$ batas waktu cukup besar; konstanta tersembunyi untuk algoritma acak adalah 4.$O(n\log n)$

• Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Noar, dan Rafail Ostrovsky. Mur dan baut yang cocok. Proc 5th Ann. ACM-SIAM Symp. Algoritma Diskrit , 690-696, 1994.
• Noga Alon, Phillip G. Bradford, dan Rudolf Fleischer. Menyamakan mur dan baut lebih cepat. Memberitahu. Proc Lett. 59 (3): 123-127, 1996.
• Phillip G. Bradford. Cocokkan mur dan baut secara optimal. Tech. Rep. MPI-I-95-1-025, Max-Planck-Institut für Informatik, 1995. http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-025
• Phillip G. Bradford dan Rudolf Fleischer. Menyamakan mur dan baut lebih cepat. Proc Ke-6 Int. Symp. Komputasi Algoritma. , 402–408, 1995. Lecture Notes Comput. Sci. 1004.
• János Komlós, Yuan Ma, dan Endre Szemerédi. Menyesuaikan mur dan baut dalam waktu . SIAM J. Discrete Math. 11 (3): 347–372, 1998.$O(n\log n)$
• Gregory J. E. Rawlins. Dibandingkan dengan Apa? : Pengantar Analisis Algoritma . Computer Science Press / WH Freeman, 1992.

Setelah Anda tidak hanya berbicara tentang waktu-poli tetapi melihat banyak model perhitungan yang kita pelajari, ada contoh di mana-mana:

Di Logspace: Konektivitas ST tidak terarah (di RL sejak 1979, dan di L hanya sejak 2005)

Dalam NC: Menemukan pencocokan sempurna dalam grafik bipartit secara paralel (dalam RNC dan masih belum diketahui berada dalam NC)

Dalam bukti interaktif: yang deterministik memberikan NP, sedangkan yang acak dapat melakukan PSPACE. Terkait: memeriksa bukti secara deterministik membutuhkan melihat semua bukti, sementara bukti PCP memungkinkan Anda untuk memeriksa hanya sejumlah bit yang konstan.

Dalam Algorithmic Mechanism Design: banyak mekanisme perkiraan kebenaran acak tanpa mitra deterministik.

Dalam kompleksitas Komunikasi: fungsi kesetaraan membutuhkan komunikasi linier secara deterministik tetapi komunikasi logaritmik (atau, tergantung pada model yang tepat, konstan) secara acak.

Dalam pohon keputusan: mengevaluasi pohon dan-atau membutuhkan kueri linier secara deterministik tetapi lebih sedikit dengan pengacakan. Ini pada dasarnya setara dengan pemangkasan alpha-beta yang memberikan algoritma sub-linear acak untuk evaluasi game-tree.

Dalam model streaming, model komputasi terdistribusi: lihat jawaban sebelumnya.

Sebagian besar algoritma streaming

Dalam model streaming perhitungan ( AMS , buku ), suatu algoritma memproses urutan pembaruan online dan dibatasi untuk menjaga ruang sublinear saja. Kapan pun waktunya, algoritma harus dapat menjawab kueri.

$t$$i_t \in [n]$$D_m = |\{i_t: t = 1\ldots m\}|$$m$$\Omega(n)$$O(\log n)$$O(\frac{1}{\epsilon^2} + \log n)$$1\pm \epsilon$

$n$$\Delta$$\min(\Omega(\log\Delta),\Omega(\sqrt{\log n}))$ yang berlaku untuk algoritma acak dan deterministik.

$u$ dapat melakukan beberapa perhitungan dan mengirim pesan lokal untuk tetangganya. Pesan-pesan ini dijamin akan diterima sebelum dimulainya babak berikutnya.)

1. $u$$1/d_u$$d_u>0$$u$$d_u=0$$u$ cukup memasuki set independen. (Awalnya, setiap node aktif.)
2. $u$$u$ memasuki set independen, menonaktifkan dirinya sendiri dan memberi tahu semua tetangganya untuk menonaktifkan diri mereka sendiri. Derajat dari node aktif yang tersisa berkurang sesuai, yaitu, semua tepi ke node yang dinonaktifkan dihapus.
3. $v$

$O(\log n)$$O(n^{1/\sqrt{\log n}})$

[1] Michael Luby: Algoritma Paralel Sederhana untuk Masalah Set Independen Maksimal. SIAM J. Comput. 15 (4): 1036-1053 (1986) http://dx.doi.org/10.1137/0215074

[2] Alessandro Panconesi, Aravind Srinivasan: Tentang Kompleksitas Dekomposisi Jaringan Terdistribusi. J. Algorithms 20 (2): 356-374 (1996) http://dx.doi.org/10.1006/jagm.1996.0017

[3] Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer: Komputasi Lokal: Batas Bawah dan Batas Atas. CoRR abs / 1011.5470 (2010) http://arxiv.org/abs/1011.5470

Pemilihan Pemimpin dalam Lingkaran Proses Anonim

$1$

Ada argumen sederhana (misalnya [1]) bahwa tidak ada algoritma pemilihan pemimpin deterministik untuk cincin anonim.

Model: Kami berasumsi bahwa perhitungan maju dalam putaran sinkron di mana, dalam setiap putaran, setiap proses melakukan beberapa perhitungan lokal, mengirim pesan ke tetangganya di atas ring, dan menerima pesan dari tetangganya.

$A$$r\ge 0$$1$

$r\ge 0$$r$$A$$r$$r$$r+1$$A$

$A$$n$$[1,n^4]$

[1] Dana Angluin: Properti Lokal dan Global dalam Jaringan Prosesor (Extended Abstract). STOC 1980: 82-93. http://doi.acm.org/10.1145/800141.804655

Masalah mayoritas dalam model kueri.

$n$$i$$j$

$n/2$$O(n)$

$O(n)$

FRK Chung, RL Graham, J. Mao, dan AC Yao, strategi tidak sadar dan adaptif untuk masalah Mayoritas dan Pluralitas, Proc. COCOON 2005 , hlm. 329–338.