Kapan BPP dengan koin bias setara dengan BPP standar?

Biarkan mesin Turing probabilistik memiliki akses ke koin yang tidak adil yang muncul di kepala dengan probabilitas (membalik independen). Tentukan sebagai kelas bahasa yang dikenali oleh mesin seperti itu dalam waktu polinomial. Ini adalah latihan standar untuk membuktikan bahwa:p B P P $p$$BPP_p$

A) Jika rasional atau bahkan -computable maka . (Dengan -computable yang saya maksud: ada algoritma polinomial acak yang diumpankan dalam pengembalian unary whp rasional biner dengan penyebut yang terletak dalam dari .)p B P P B P P p = B P P B P P n 2 n 2 - n - 1$p$$BPP$$BPP_p=BPP$$BPP$$n$$2^n$$2^{-n-1}$$p$

B) Untuk beberapa tidak dapat dihitung , kelas berisi bahasa yang tidak dapat dan karenanya lebih besar dari . Nilai-nilai membentuk set padat di .p B P P p B P P p ( 0 , 1 $p$$BPP_p$$BPP$$p$$(0,1)$

Pertanyaan saya adalah sebagai berikut: apa yang terjadi di antara keduanya? Apakah ada kriteria untuk ? Khususnya:$BPP_p=BPP$

1) Apakah probabilitas tidak dapat dihitung ada sehingga ? (Mereka mungkin dapat dihitung di beberapa kelas yang lebih tinggi).B P P p B P P p = B P $BPP$$p$$BPP_p=BPP$

2) Apakah lebih luas dari untuk semua tidak dapat dihitung ? (Parameter yang dimaksud adalah parameter yang ekspansi binernya mengandung urutan nol dan / atau yang sangat panjang. Dalam hal ini, komputasi bit dengan pengambilan sampel acak mungkin memakan waktu yang sangat lama, bahkan waktu yang tidak dapat dihitung, dan masalahnya tidak dapat dipulihkan ke waktu polinomial. kesulitan dapat diatasi dengan basis ekspansi lain, tetapi tertentu mungkin menipu semua basis).B P P p B P P p $BPP_p$$BPP$$p$$p$

1) Ya, tetapi hanya karena definisi Anda. Ambil bahasa unary L ∈ E X P ∖ B P P (ya, saya tahu ini mungkin kosong, dalam hal ini hanya mengambil sesuatu yang lebih besar dari E X P ), yang sangat jarang dalam arti bahwa n ∉ L jika n bukan menara 2 ′ s , yaitu, dari bentuk 2 2 2 … . Tentukan p = Σ n ∈ L 1 / n . Ini p tidak $L\in EXP\setminus BPP$$EXP$$n\notin L$$n$$2's$$2^{2^{2^\ldots}}$$p=\sum_{n\in L} 1/n$$p$P P -computable, tapi p dapat didekati di P hingga kesalahan aditif cukup kecil yang memungkinkan simulasi dari B P P p mesin.$BPP$$p$$P$$BPP_p$

Memiliki Anda didefinisikan B P P -computable seperti yang Anda ingin perkiraan p hingga kesalahan aditif dari 1 / n (bukan 1 / 2 n ) dalam waktu polinomial, hal akan berbeda.$BPP$$p$$1/n$$1/2^n$

Memperbarui. Jawaban di bawah adalah untuk kasus ketika kesalahan aditif yang kami izinkan adalah 2 - n bukannya 2 - n - 1 .$2^{-n}$$2^{-n-1}$

2) Ya, karena di sini Anda bisa melupakan pembatasan polinomial pada kelas dan dengan mengambil sampel 2 n kali Anda bisa mendapatkan bit ke- n p dalam B P P p .$2^n$$n$$p$$BPP_p$