Menjalankan algoritma BPP dengan string setengah-acak, setengah-permusuhan

Pertimbangkan model berikut: string n-bit r = r ₁ ... 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 ingin.

Pertanyaan saya adalah ini: dapatkah string yang dihasilkan (sebut saja r ') digunakan oleh algoritma RP atau BPP sebagai satu-satunya sumber keacakan? Asumsikan bahwa musuh mengetahui terlebih dahulu seluruh algoritma BPP, string r, dan himpunan A, dan bahwa ia memiliki waktu komputasi yang tidak terbatas. Juga berasumsi (jelas) bahwa algoritma BPP tidak mengetahui keputusan balik musuh atau A.

Saya sangat menyadari bahwa ada garis panjang pekerjaan pada pertanyaan semacam ini, dari karya Umesh Vazirani pada sumber semi-acak (model yang berbeda tetapi terkait), hingga pekerjaan yang lebih baru pada ekstraktor, merger, dan kondensor. Jadi pertanyaan saya hanyalah apakah pekerjaan itu menghasilkan hal yang saya inginkan! Literatur tentang sumber acak yang lemah begitu besar, dengan begitu banyak model yang agak berbeda, sehingga seseorang yang mengetahui bahwa literatur mungkin dapat menghemat banyak waktu. Terima kasih sebelumnya!

Yang Anda butuhkan adalah "seeded extractor" dengan parameter berikut: seed of length , randomness crude n / 2 , dan output length n Ω ( 1 ) . Ini sudah diketahui. Meskipun saya tidak mengetahui survei terbaru, saya percaya bahwa bagian 3 dari survei Ronen sudah cukup.$O(\log n)$$n/2$$n^{\Omega(1)}$

$2^{-n/2}$

Apakah musuh diizinkan untuk melihat seluruh string r sebelum memutuskan bagaimana mengatur bit dalam A? Jika jawabannya tidak maka ini adalah sumber bit-fixing, yang sebenarnya dapat diekstraksi secara deterministik. Artinya, tidak diperlukan benih yang benar-benar acak. Lihat, misalnya, Kamp dan Zuckerman untuk konstruksi ekstraktor untuk sumber pengaturan bit.

Jika musuh dibiarkan melihat sisa string saya masih akan menebak bahwa itu dapat diekstraksi secara deterministik, tetapi modelnya sedikit berbeda dan saya tidak tahu dari atas kepala saya bagaimana mereka berhubungan. Karena himpunan A adalah acak itu sebenarnya lebih ramah daripada sumber bit-fixing, di mana himpunan A mungkin sewenang-wenang.

Noam benar, tentu saja. Secara historis, simulasi pertama BPP dengan sumber tingkat entropi konstan diberikan dalam makalah saya "Mensimulasikan BPP Menggunakan Sumber Acak Lemah Umum." Sekarang ada cara yang lebih sederhana untuk mencapai ini dan hasil yang lebih kuat.

Ekstraksi deterministik lebih dari jumlah bit yang konstan tidak mungkin dalam model Anda. (Anda bisa mendapatkan ekstraksi deterministik lemah 1 bit hanya dengan mengeluarkan bit pertama.) Kamp dan saya menunjukkan bahwa tidak mungkin untuk mengekstraksi lebih dari jumlah bit yang konstan dalam sumber fixing bit umum yang tidak dilupakan dengan laju entropi yang konstan, tetapi karena himpunan A adalah acak, hasil tersebut tidak berlaku seperti yang dinyatakan. Namun, bukti kami bekerja dengan memilih A secara acak dari ukuran tetap t, jadi dengan memilih t = .6n, katakanlah, hasil untuk acak acak A akan mengikuti.