Apakah BPP vs P merupakan masalah nyata setelah kita tahu BPP terletak pada P / poli?

Kami tahu (untuk saat ini sekitar 40 tahun, terima Adleman, Bennet dan Gill) bahwa masuknya BPP P / poli, dan bahkan lebih kuat BPP / poli P / poli ditahan. "/ Poli" berarti bahwa kita bekerja secara tidak seragam (sirkuit terpisah untuk setiap panjang input ), sementara P tanpa "/ poli" ini berarti kita memiliki satu mesin Turing untuk semua panjang input yang mungkin , bahkan lebih lama dari, katakanlah, = jumlah detik ke "Big Bang" berikutnya.$\subseteq$ $\subseteq$ $n$$n$$n$

Pertanyaan 1: Apa yang baru yang akan menjadi bukti (atau penolakan) BPP = P berkontribusi untuk pengetahuan kita setelah kita mengetahui BPP P / poly? $\subseteq$

Di bawah "baru" yang saya maksud adalah konsekuensi yang benar-benar mengejutkan, seperti runtuhnya / pemisahan kelas kompleksitas lainnya. Bandingkan ini dengan konsekuensi yang akan diberikan bukti / non-aktifkan NP P / poly. $\subseteq$

[TAMBAH 08.10.2017]: Satu konsekuensi yang sangat mengejutkan dari BPP P adalah bahwa, seperti yang ditunjukkan oleh Impagliazzo dan Wigderson , semua masalah (!) Di E = DTIME [2 ^ {O (n)}] akan memiliki sirkuit berukuran 2 ^ {o (n)} . Terima kasih kepada Ryan karena mengingat hasil ini.$\not\subseteq$ 2 o ( n $[2^{O(n)}]$$2^{o(n)}$

Pertanyaan 2: Mengapa kami tidak dapat membuktikan BPP = P sepanjang garis yang sama dengan bukti BPP / poly $\subseteq$ P / poly?

Satu "jelas" kendala adalah masalah domain terbatas hingga tak terbatas: sirkuit boolean bekerja di atas domain terbatas , sedangkan mesin Turing bekerja di seluruh set $\{0,1\}^*$ dari $0$ - $1$ string dengan panjang berapa pun. Jadi, untuk derandomisasi sirkuit boolean probabilistik, cukup untuk mengambil sebagian besar salinan independen dari sirkuit probabilistik, dan untuk menerapkan ketimpangan Chernoff, bersama dengan ikatan serikat pekerja. Tentu saja, di atas domain tak terbatas , aturan mayoritas sederhana ini tidak akan berfungsi.

Tetapi apakah ini (domain tanpa batas) benar-benar "penghalang"? Dengan menggunakan hasil dari teori belajar statistik (dimensi VC), kita sudah dapat membuktikan bahwa BPP / poly P / poly juga berlaku untuk sirkuit yang bekerja pada domain tak terbatas , seperti sirkuit aritmatika (bekerja pada semua bilangan real); lihat misalnya makalah Cucker ini di al. Ketika menggunakan pendekatan yang serupa, yang kita perlukan adalah menunjukkan bahwa dimensi VC dari mesin Turing poli-waktu tidak boleh terlalu besar. Adakah yang melihat upaya untuk melakukan langkah terakhir ini? $\subseteq$

Hasilnya (dikenal sebagai konvergensi seragam dalam probabilitas ) kemudian menyiratkan yang berikut: jika untuk setiap input , fungsi yang dipilih secara acak (di bawah beberapa distribusi probabilitas pada ) memenuhi untuk konstanta , maka dapat dihitung pada semua input sebagai mayoritas dari beberapa (tetap) fungsi dari . Lihat, misalnya, Corollary 2 dalam makalah Haussler . [Agar ini bisa bertahan, ada beberapa kondisi terukur ringan pada ] $x\in X$$\mathbf{f}\in F$$F$$\mathrm{Prob}\{\mathbf{f}(x)=f(x)\}\geq 1/2+c$$c>0$$f(x)$$x\in X$$m=O(v)$$F$$F$

Misalnya, jika adalah himpunan semua polinomial dihitung oleh sirkuit aritmatika ukuran , maka semua polinomial di memiliki derajat paling banyak . Dengan menggunakan batas atas yang diketahui pada jumlah nol pola polinomial (lihat, misalnya makalah ini ), orang dapat menunjukkan bahwa dimensi VC dari adalah . Ini menyiratkan dimasukkannya BPP / poli P / poli untuk sirkuit aritmatika.$F$$f:\mathbb{R}^n\to\mathbb{R}$$\leq s$$F$$D=2^s$$F$$O(n\log D)=O(ns)$$\subseteq$

Tidak yakin berapa banyak jawaban ini, saya hanya menikmati beberapa perenungan.

Pertanyaan 1 dapat ditanyakan secara setara tentang P NP dan dengan jawaban yang sama - teknik / ide yang digunakan untuk membuktikan hasilnya akan menjadi terobosan besar lebih dari kesimpulan itu sendiri.$\neq$

Untuk Pertanyaan 2 saya ingin berbagi latar belakang dan pemikiran. Hampir semua teknik dan ide yang kami miliki untuk BPP = P, sejauh yang saya ketahui, melalui "derandomisasi": Dengan adanya Mesin Turing polytime probabilistik, buatlah PRG untuk mengumpankannya sejumlah bit yang ditentukan secara deterministik alih-alih acak. yang, sehingga perilakunya sangat mirip dengan perilakunya pada bit yang benar-benar acak. Jadi dengan generator pseudorandom yang cukup baik, kami mendapatkan BPP = P. ("Dunia BPP = P" Goldreich memberikan bukti bahwa bukti BPP = P harus sama dengan ini.)

Ini hampir sepanjang garis BPP P / poli, kecuali di sana, PRG adalah string saran yang dihasilkan oleh sihir. Mungkin jawaban terbaik untuk Pertanyaan 2 Anda adalah bahwa di P kami tidak memiliki sihir dan harus membuat saran sendiri. Derandomisasi juga merupakan ide di balik hasil 2004 SL = L, menggunakan alat seperti grafik expander.$\subseteq$

Sekarang pertimbangkan apa bukti seperti itu akan menyiratkan hanya satu algoritma tertentu, tes primality Miller-Rabin. Ini akan menunjukkan adanya beberapa generator deterministik yang memilih urutan bilangan bulat untuk dimasukkan ke dalam uji primitif Miller-Rabin sedemikian rupa sehingga, jika dan hanya jika semua bilangan bulat berlalu, maka bilangan asli adalah bilangan prima.

Seperti yang saya pahami (walaupun saya bukan ahli), pertanyaan apakah daftar seperti itu ada dan seberapa kecil angka di dalamnya (khususnya jika cukup untuk memeriksa semua angka di bawah beberapa ikatan) tampaknya pertanyaan yang cukup dalam di teori bilangan dan terkait erat dengan pembuktian bentuk Hipotesis Riemann yang digeneralisasi. Lihat pertanyaan ini . Saya tidak berpikir ada implikasi formal di sini, tapi sepertinya bukan sesuatu yang kita harapkan minggu depan sebagai konsekuensi miniatur kebetulan dari konstruksi PRG yang jauh lebih umum.