Untuk R oracle acak, apakah BPP sama dengan set bahasa yang dapat dihitung dalam P ^ R?

Nah, judulnya cukup banyak mengatakan itu semua. Pertanyaan menarik di atas ditanyakan oleh komentator Jay di blog saya (lihat di sini dan di sini ). Saya menduga keduanya bahwa jawabannya adalah ya dan bahwa ada bukti yang relatif sederhana, tetapi saya tidak dapat melihatnya begitu saja. (Namun, secara kasar, orang dapat mencoba menunjukkan bahwa, jika bahasa dalam tidak ada dalam , maka ia harus memiliki informasi timbal balik algoritme tak terhingga dengan , dalam hal ini bahasa itu tidak dapat dihitung. Juga, perhatikan bahwa satu arah sepele: bahasa yang dapat dihitung dalam tentu mengandung .) B P P R P R B P $P^R$$BPP$$R$$P^R$ $BPP$

Perhatikan bahwa saya tidak bertanya tentang kelas AlmostP , yang terdiri dari bahasa-bahasa yang ada di untuk hampir setiap (dan dikenal dengan sama ). Dalam pertanyaan ini, pertama kita memperbaiki , kemudian melihat sekumpulan bahasa dihitung di . Di sisi lain, orang dapat mencoba untuk menunjukkan bahwa, jika bahasa dalam dapat dihitung, bahkan untuk oracle acak tetap , maka sebenarnya bahasa itu harus dalam . R B P P R P R P R R A L m o s t $P^R$$R$$BPP$$R$$P^R$$P^R$$R$$AlmostP$

Pertanyaan yang berhubungan erat adalah apakah, dengan probabilitas 1 di atas acak , kami miliki$R$

$AM = NP^R \cap Computable.$

Jika demikian, maka kita mendapatkan konsekuensi menarik berikut: jika , maka dengan probabilitas 1 di atas oracle acak , satu-satunya bahasa yang menyaksikan pemisahan oracle adalah bahasa yang tidak dapat diperhitungkan.R P R ≠ N P $P=NP$$R$$P^R \ne NP^R$

Iya.

Pertama, karena saya sendiri perlu memikirkannya sendiri, izinkan saya meresmikan perbedaan antara pertanyaan Anda dan ; itu adalah urutan bilangan. , dan hasil yang Anda singgung adalah . Jika saya mengerti dengan benar, Anda bertanya apakah .A l m o s t P : = { L : P r R ( L ∈ P R ) = 1 } ∀ $\mathsf{AlmostP}$$\mathsf{AlmostP} := \{L : Pr_R(L \in \mathsf{P}^R) = 1\}$P r R ( ∀ $\forall L\, L \in \mathsf{BPP} \iff Pr_R(L \in \mathsf{P}^R) = 1$$Pr_R(\forall L\, L \in \mathsf{P}^R \cap \mathsf{COMP} \iff L \in \mathsf{BPP}) = Pr_R(\mathsf{P}^R \cap \mathsf{COMP} = \mathsf{BPP}) = 1$

Mempertimbangkan

$p := 1-Pr_R(\mathsf{P}^R\cap \mathsf{COMP} = \mathsf{BPP}) = Pr_R(\exists L \in \mathsf{P}^R \cap \mathsf{COMP} \backslash \mathsf{BPP})$ .

Dengan ikatan serikat, dibatasi oleh . (Perhatikan bahwa jumlah yang terakhir dapat dihitung.) Sekarang, dengan undang-undang 0-1 - yang berlaku karena semua pernyataan yang relevan tidak berubah jika kita mengubah secara berlebihan - setiap probabilitas individu dalam jumlah ini adalah 0 atau 1. Jika jawaban untuk pertanyaan Anda adalah tidak, maka , jadi harus ada beberapa sedemikian rupa sehingga . Tetapi ini bertentangan dengan fakta bahwa .∑ L ∈ C O M P P r R ( L ∈ P R ∖ B P P ) R p = 1 L ∈ C O M P P r R ( L ∈ P R ∖ B P P ) = 1 A l m o s t P = B P $p$$\sum_{L \in \mathsf{COMP}} Pr_R(L \in \mathsf{P}^R \backslash \mathsf{BPP})$$R$$p=1$$L \in \mathsf{COMP}$$Pr_R(L \in \mathsf{P}^R \backslash \mathsf{BPP}) = 1$$\mathsf{AlmostP} = \mathsf{BPP}$

Pembaruan 10 Okt 2014 : Seperti yang ditunjukkan dalam komentar oleh Emil Jeřábek, argumen yang sama berlaku untuk vs. , karena kita juga tahu bahwa .N P R A l m o s t N P = A $\mathsf{AM}$$\mathsf{NP}^R$$\mathsf{AlmostNP} = \mathsf{AM}$

Dia juga menunjukkan bahwa kami tidak menggunakan apa pun tentang selain itu adalah kelas yang dapat dihitung yang berisi (resp., ). Jadi "kesimpulan menarik" dalam OQ sebenarnya berlaku untuk setiap kelas bahasa yang dapat dihitung yang berisi : if , "hanya" bahasa yang menyaksikan pemisahan oracle berada di luar . Tetapi pernyataan terakhir terasa agak menyesatkan bagi saya (itu membuatnya terdengar seperti, untuk setiap bisa kita pertimbangkanB P P A M C A M P = N P P R ≠ N P R C L 0 C = A M ∪ { L 0 } L 0 N P R ≠ P$\mathsf{COMP}$$\mathsf{BPP}$$\mathsf{AM}$$\mathcal{C}$$\mathsf{AM}$$\mathsf{P} = \mathsf{NP}$$\mathsf{P}^R \neq \mathsf{NP}^R$$\mathcal{C}$$L_0$$\mathcal{C} = \mathsf{AM} \cup \{L_0\}$ , dan dengan demikian "menunjukkan" bahwa tidak ada menyadari , bertentangan dengan yang terkenal dalil). Alih-alih, menuliskannya secara simbolis, kami telah menunjukkan:$L_0$$\mathsf{NP}^R \neq \mathsf{P}^R$

Jika , maka . ∀ dapat dihitung  C ⊇ A $\mathsf{P} = \mathsf{NP}$$\forall \text{countable } \mathcal{C} \supseteq \mathsf{AM}\, Pr_R(\mathsf{NP}^R \neq \mathsf{P}^R \text{ and } \mathsf{NP}^R \cap \mathcal{C} = \mathsf{P}^R \cap \mathcal{C}) = 1$

Perhatikan bahwa, yang paling penting, probabilitas 1 bukan hal yang sama dengan semua , dan set lengkap memenuhi argumen ke dapat bergantung pada . Jadi, jika kita mencoba mengubah menjadi , paling banyak menghapus set 0 set yang memenuhi pernyataan ini.R P r R C C C ∪ { L 0 } $R$$R$$Pr_R$$\mathcal{C}$$\mathcal{C}$$\mathcal{C} \cup \{L_0\}$$R$

Sementara urutan bilangan antara apa yang Anda minta dan hampir P berbeda, tidak terlalu sulit untuk menunjukkan bahwa mereka setara. Pertama, untuk setiap L tetap, pertanyaan apakah L \ dalam P ^ O tidak tergantung pada segmen awal terbatas O. maka kemungkinan bahwa L \ dalam P ^ R adalah 0 atau 1. Dari hampir - Hasil P, untuk setiap L yang dapat dihitung tidak dalam BPP, jawabannya adalah 0, sedangkan jika L \ dalam BPP, probabilitasnya adalah 1. Karena ada banyak L yang dapat dihitung, kita dapat melakukan ikatan gabungan; gabungan yang dapat dihitung dari probabilitas 0 set memiliki probabilitas 0. Dengan demikian, probabilitas bahwa ada L yang dapat dihitung yang tidak ada dalam BPP tetapi dalam P ^ R adalah 0, seperti probabilitas bahwa ada bahasa dalam BPP bukan dalam P ^ R,