Buktikan atau bantah: BPP (0.90,0.95) = BPP

Saya benar-benar ingin bantuan Anda dengan membuktikan atau menyangkal klaim berikut: . Dalam teori kompleksitas komputasi, BPP, yang berarti waktu polinom probabilitas terbatasi-kesalahan adalah kelas masalah keputusan yang dipecahkan oleh mesin Turing probabilistik dalam waktu polinomial, dengan probabilitas kesalahan paling banyak untuk semua contoh . .$BPP(0.90,0.95)=BPP$$\frac{1}{3}$$BPP=BPP(\frac{1}{3},\frac{2}{3})$

Tidak langsung bahwa salah satu set adalah subset dari yang lain, karena jika probabilitas untuk kesalahan lebih kecil dari itu tidak harus lebih kecil dari dan jika itu lebih besar dari tidak harus lebih besar dari .$0.9$$\frac{1}{3}$$\frac{2}{3}$$0.905$

Saya mencoba menggunakan ketidaksetaraan Chernoff untuk membuktikan klaim, saya tidak yakin persis bagaimana caranya. Saya sangat membutuhkan bantuan Anda. Apakah ada klaim umum tentang hubungan ini yang dapat saya gunakan?

Untuk memperluas komentar saya menjadi jawaban: bentuk multiplikasi dari batas Chernoff mengatakan bahwa jika ekspektasi untuk jumlah variabel biner acak independen adalah , maka probabilitas tersesat ' terlalu jauh dari harapan itu berjalan sebagai: .$X=\sum_{i=0}^n X_i$$\mu$$Pr(X\gt (1+\delta)\mu) \lt \left(\dfrac{e^\delta}{(1+\delta)^{(1+\delta)}}\right)^\mu$

Sekarang, bayangkan prosedur di mana, diberikan string untuk diuji, kami menjalankan percobaan dari kami algoritma (untuk beberapa akan dipilih nanti) dan menerima iff setidaknya dari percobaan tersebut menerima . Kita dapat menggunakan ikatan Chernoff untuk menemukan probabilitas kegagalan dalam hal sebagai berikut:$\sigma$$n$$BPP(0.90, 0.95)$$n$$0.925n$$\sigma$$n$

Biarkan menunjukkan hasil uji coba ke- , dan dengan demikian jumlah uji coba yang berhasil. Kita dapat mengasumsikan secara konservatif bahwa probabilitas kita untuk positif palsu adalah ; ini berarti bahwa jika kita membuat percobaan independen pada string , jumlah keberhasilan yang diharapkan adalah . (Perhatikan bahwa probabilitas positif palsu kurang dari akan mengarah pada nilai yang diharapkan lebih rendah dan dengan demikian bahkan lebih ketat pada perkiraan yang akan datang.) Sekarang, mari kita lihat probabilitas bahwa kita memiliki lebih dari positif palsu (yaitu , ). Kami ambil$X_i$$i$$X=\sum X_i$$.9$$n$$\sigma\notin L$$\mu = E(X) = 0.9n$$.9$$0.925n$$X\gt 0.925n$$\delta = \left(\frac{0.925}{0.9}\right)-1 =\frac{1}{36}$ ; lalu jadi kita harus .$\left(\dfrac{e^\delta}{(1+\delta)^{(1+\delta)}}\right) \approx.99961\lt \frac{2999}{3000}$$Pr(X\gt 0.925n)\lt\left(\frac{2999}{3000}\right)^{0.9n}$

Dari sini harus jelas bahwa dengan mengambil cukup besar kita dapat mengurangi probabilitas ini menjadi . Jadi, untuk cukup besar ini , jika kita menerima string hanya jika jumlah percobaan yang sukses pada lebih besar dari , maka probabilitas kita untuk menerima string turun di bawah . Perhatikan bahwa ini konstan , tidak tergantung pada ukuran masalah kita; karena kita menjalankan polinomial kami$n$$\lt\frac{1}{3}$$n$$\sigma$$\sigma$$.925n$$\sigma\notin L$$\frac{1}{3}$$n$$BPP(0.9, 0.95)$algoritma beberapa kali konstan, total waktu berjalan dari prosedur baru kami masih polinomial. Analisis serupa yang mengarah ke arah lain akan menunjukkan bahwa probabilitas 'false negative' (bahwa untuk string yang ada dalam bahasa kita) akan dibatasi oleh untuk beberapa , dan lagi-lagi kita dapat ambil cukup besar untuk mengikat probabilitas negatif palsu oleh (atau, dengan kata lain, untuk memastikan setidaknya probabilitas menerima pada string ). Ini menunjukkan bahwa$X\lt.925n$$c^n$$c$$n$$\frac{1}{3}$$\frac{2}{3}$$\sigma\in L$$BPP(.9, .95)\subseteq BPP(\frac13, \frac23) \equiv BPP$, dan komentar Yuval menunjukkan bagaimana membuktikan kesetaraan terbalik melalui prosedur serupa.

Canonically, ini dikenal sebagai amplifikasi probabilitas dan ini merupakan metode yang sangat berguna untuk berurusan dengan kelas probabilistik. Konstanta spesifik kurang penting, jelas, maka fakta bahwa ikatan Chernoff membuat kita mengikat probabilitas 'hasil salah' kita dengan beberapa fungsi eksponensial dari sejumlah uji coba, sehingga mereka dapat dibuat kecil secara sewenang-wenang dengan hanya sejumlah kecil uji coba.