Algoritma acak yang “terlihat” deterministik?

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 algoritma deterministik untuk masalah ini?

Secara khusus, saya bertanya-tanya apakah ada algoritma untuk menemukan bilangan prima antara n dan 2n. Tidak ada algoritma deterministik waktu polinomial yang diketahui. Ada algoritma acak sepele yang bekerja hanya dengan mengambil sampel bilangan bulat acak dalam interval, yang bekerja berkat teorema bilangan prima . Tapi apakah ada algoritma dari jenis di atas yang waktu tayang yang diharapkan antara ini?

EDIT: Untuk mempersempit pertanyaan saya sedikit, saya ingin algoritma seperti itu untuk masalah di mana ada banyak kemungkinan hasil yang benar, namun algoritma acak bergantung pada satu independen dari keacakannya. Saya menyadari bahwa pertanyaannya mungkin tidak sepenuhnya ditentukan ...

Shafi Goldwasser mengomunikasikan kepada saya bahwa dia dan rekan penulisnya telah menyelidiki dengan tepat algoritma semacam itu untuk masalah teori angka! Berikut ini diketahui:

1. Lenstra telah menunjukkan bahwa ada suatu algoritma untuk menemukan mod non-residu kuadratik yang prima.

2. Gat dan Goldwasser telah menunjukkan bahwa ada suatu algoritma untuk menemukan generator , di mana p adalah prima bentuk 2 q + 1 untuk q prima .$\mathbb{Z}_p^*$$p$$2q + 1$$q$

(Saya tidak tahu referensi citable.) Ada juga penelitian yang sedang berlangsung pada pertanyaan yang saya tanyakan tentang menemukan prima antara dan 2 n .$n$$2n$

EDIT: Makalah oleh Gat dan Goldwasser sekarang diterbitkan: http://eccc.hpi-web.de/report/2011/136/ . Makalah ini meskipun tidak menyelesaikan pertanyaan menemukan bilangan prima antara dan 2 n .$n$$2n$

Apakah struktur data acak dihitung?

Ada daftar lewati yang merupakan struktur data peta asosiatif diurutkan.

Waktu berjalannya untuk operasi umum seperti penyisipan, pengambilan dan penghapusan adalah (dalam kasus yang diharapkan) setara dengan yang ada di pohon pencarian seimbang - yaitu . Namun, struktur data kadang-kadang diklaim memiliki faktor konstan yang jauh lebih baik daripada implementasi pohon pencarian bila dilakukan dengan benar (ini bergantung pada sumber keacakan yang baik dan efisien). Faktor konstan yang lebih baik mungkin hasil dari kenyataan bahwa tidak ada penyeimbangan kembali (atau operasi serupa) harus dilakukan.$O(\log n)$

Bagaimana dengan algoritma simpleks polinomial-waktu Kelner dan Spielman yang diacak? Ia menemukan titik optimal dari program linier. Tidak ada algoritma simpleks deterministik diketahui yang terbukti berjalan dalam waktu polinomial, dan bagi banyak dari mereka, contoh patologis dapat dibangun yang membuat algoritma membutuhkan waktu eksponensial.

Tentu saja, ada algoritma titik-interior polinomial-waktu, jadi bukan yang Anda cari.

Pertimbangkan pohon biner lengkap dengan semua daun yang mengandung 0, kecuali satu daun yang berisi 1. Tugasnya adalah menemukan daun yang mengandung 1. Terhadap algoritma pencarian deterministik apa pun dimungkinkan untuk membangun keluarga pohon tak terbatas (satu untuk setiap n ) yang algoritma harus memeriksa setiap daun. Jadi untuk keluarga kasus terburuk ini algoritma deterministik diharapkan runtime 2 n .$2^n$$n$$2^n$

Sekarang pertimbangkan sebuah algoritma yang secara acak memilih daun pertama secara seragam secara acak, dan kemudian memeriksa semua daun berturut-turut secara deterministik (membungkus ke awal). Ini akan menemukan angka 1 setelah memeriksa setengah dari semua daun, rata-rata. Jadi algoritma acak diharapkan runtime .$2^{n-1}$

Apakah ini memenuhi syarat?

Algoritma faktorisasi polinomial mungkin merupakan jenis contoh yang Anda cari. The Cantor-Zassenhaus algoritma menggunakan keacakan untuk menghitung (skala upto unik) faktor polinomial irreducible dari polinom satu variabel diberikan atas lapangan terbatas dalam waktu polinomial dalam ukuran input dan log p . Jika Anda benar-benar ingin masalah memiliki jawaban yang unik, Anda dapat meminta faktor prima irreducible monin polinomial. Sejauh yang saya tahu, tidak diketahui bagaimana memfaktorkan waktu polinomial deterministik kecuali p dijamin kecil.$\mathbb{F}_p$$\log p$$p$

$\log p$

Ada proyek polymath yang menjawab pertanyaan terkait: http://michaelnielsen.org/polymath1/index.php?title=Finding_primes

Mengenai pertanyaan pertama Anda, saya memikirkan Quicksort terlebih dahulu tetapi itu harus jelas.

Ada algoritma pencocokan string ( Nebel, 2006 ) yang menggunakan ide probabilistik. Saya tahu apakah ini adalah pendekatan tercepat yang ada, dan Anda tampaknya perlu beberapa sampel untuk pelatihan.

Makalah STACS '97 berikut mungkin menarik untuk kasus Anda: Kompleksitas Membuat Instans Uji .

Abstrak: Baru-baru ini, Watanabe mengusulkan kerangka kerja baru untuk menguji kebenaran dan perilaku kasus rata-rata algoritma yang dimaksudkan untuk memecahkan masalah pencarian NP yang diberikan rata-rata secara efisien. Idenya adalah untuk secara acak menghasilkan contoh bersertifikat dengan cara yang menyerupai distribusi yang mendasarinya. Kami membahas pendekatan ini dan menunjukkan bahwa contoh pengujian dapat dibuat untuk setiap masalah pencarian NP dengan pertanyaan non-adaptif ke oracle NP. Lebih lanjut, kami memperkenalkan jenis generator instance uji Las Vegas serta Monte Carlo dan menunjukkan bahwa generator ini dapat digunakan untuk mengetahui apakah suatu algoritma rata-rata benar dan efisien. Sebenarnya, tidak sulit untuk membangun generator Monte Carlo untuk semua masalah pencarian RP serta generator Las Vegas untuk semua masalah pencarian ZPP. Di samping itu,

Khususnya, lihat halaman 384, di bawah Corollary 12:

$\rm{ZPP}$$\rm{RP}$$\rm{ZPP}$$\rm{NP}$$\rm{NP} \cap \rm{coNP}$

$\frac{1}{n^c}$$\text{polylog}(n)$