Pemahaman konkret tentang perbedaan antara definisi PP dan BPP

9

Saya bingung tentang bagaimana PP dan BPP didefinisikan. Mari kita asumsikan adalah fungsi karakteristik untuk bahasa . M menjadi Mesin Turing probabilistik. Apakah definisi berikut ini benar: $\chi$ $\mathcal{L}$
$BPP =\{\mathcal{L} :Pr[\chi(x) \ne M(x)] \geq \frac{1}{2} + \epsilon \quad \forall x \in \mathcal{L},\ \epsilon > 0 \}$
$PP =\{\mathcal{L} :Pr[\chi(x) \ne M(x)] > \frac{1}{2} \}$

Jika definisi salah, silakan coba lakukan perubahan minimal untuk membuatnya benar (yaitu jangan memberikan definisi setara lainnya yang menggunakan mesin hitung atau beberapa model yang dimodifikasi). Saya tidak dapat membedakan dengan benar kondisi pada probabilitas pada kedua definisi.

Beberapa contoh konkret dengan wawasan yang jelas tentang poin-poin halus akan sangat membantu.

complexity-theory terminology randomized-algorithms complexity-classes DurgaDatta
sumber

10

Itu terlihat benar bagi saya. Perbedaan antara BPP dan PP adalah bahwa untuk BPP probabilitas harus lebih besar dari $1/2$ oleh konstanta , sedangkan untuk PP itu bisa . Jadi untuk masalah BPP Anda dapat melakukan amplifikasi probabilitas dengan sejumlah kecil pengulangan, sedangkan untuk masalah PP umum Anda tidak bisa. $1/2+ 1/2^n$

adrianN
sumber

12

Jawaban Vor memberikan definisi standar. Biarkan saya mencoba menjelaskan perbedaannya sedikit lebih intuitif.

Misalkan adalah algoritma probabilistik polinomial-waktu kesalahan terbatas untuk bahasa yang menjawab dengan benar dengan probabilitas setidaknya $M$ $L$ . Biarkanmenjadi input dan $p\geq\frac{1}{2}+\delta$ $x$ ukuran input. $n$

Apa yang membedakan sewenang-wenang algoritma dari algoritma adalah gap positif antara probabilitas untuk menerima dan probabilitas untuk menerima . $\mathsf{PP}$ $\mathsf{BPP}$ $x\in L$ $x\notin L$ Hal penting tentang adalah bahwa kesenjangannya setidaknya . Saya akan mencoba menjelaskan mengapa perbedaan ini penting dan memungkinkan kita untuk mempertimbangkan untuk dianggap sebagai algoritma yang efisien (bahkan diperkirakan sama dengan ) sedangkan $\mathsf{BPP}$ $n^{-O(1)}$ $\mathsf{BPP}$ $\mathsf{P}$ $\mathsf{PP}$ dianggap tidak efisien (sebenarnya berisi $\mathsf{PP}$ $\mathsf{NP}$ ). Semua ini berasal dari celah ini.

Mari kita mulai dengan melihat lebih hati-hati. $\mathsf{PP}$

Perhatikan bahwa jika suatu algoritma menggunakan paling banyak bit acak selama eksekusi dan probabilitas kesalahan lebih kecil dari maka probabilitas kesalahan sebenarnya , tidak mungkin ada pilihan bit acak yang akan buat jawaban algoritma salah. $r(n)$ $2^{-r(n)}$ $0$

Lebih jauh lagi, suatu algoritma dengan running time tidak dapat menggunakan lebih dari bit acak, jadi jika kesalahan algoritma probabilistik dengan case-run-time terburuk lebih baik daripada $t(n)$ $t(n)$ $t(n)$

Dengan argumen yang sama kita dapat menunjukkan bahwa kasus di mana perbedaan antara probabilitas menerima dan probabilitas menerima terlalu kecil mirip dengan kasus di mana kita hampir tidak memiliki perbedaan. seperti dalam kasus . $x\in L$ $x\notin L$ $\mathsf{PP}$

Sekarang mari kita beralih ke . $\mathsf{BPP}$

Dalam algoritma probabilistik, kita dapat meningkatkan probabilitas untuk menjawab dengan benar. Katakanlah kita ingin meningkatkan probabilitas kebenaran menjadi untuk mengatakan probabilitas kesalahan $1-\epsilon$ $\epsilon=2^{-n}$ (kesalahan kecil secara eksponensial).

Idenya sederhana: lari $M$ beberapa kali dan ambil jawaban mayoritas.

Berapa kali kita menjalankan untuk mendapatkan probabilitas kesalahan paling banyak ? $M$ $\epsilon$ $\Theta(\delta^{-1} \lg \epsilon)$ kali. Buktinya diberikan di bagian bawah jawaban ini.

Sekarang mari kita pertimbangkan bahwa algoritma yang kita diskusikan harus polinomial-waktu. Itu berarti bahwa kita tidak dapat menjalankan lebih dari berkali-kali secara polinomi. Dengan kata lain, $M$ $\Theta(\delta^{-1} \ln \epsilon) = n^{O(1)}$ , atau lebih sederhana

δ^{- 1} \lg ϵ = n^{O (1)}

$\delta^{-1} \lg \epsilon = n^{O(1)}$

Relasi ini mengkategorikan algoritma probabilitas kesalahan terbatas ke dalam kelas tergantung pada probabilitas kesalahan mereka. Tidak ada perbedaan antara probabilitas kesalahan menjadi atau konstanta positif (yaitu tidak berubah dengan ) atau $\epsilon$ $2^{-n}$ $n$ $\frac{1}{2}-n^{O(1)}$ . Kita dapat berpindah dari yang satu ini ke yang lainnya sambil tetap berada di dalam waktu polinomial.

Namun jika terlalu kecil, katakan , , atau bahkan maka kita tidak memiliki cara untuk meningkatkan probabilitas kebenaran dan mengurangi probabilitas kesalahan cukup untuk masuk ke $\delta$ $0$ $2^{-n}$ $n^{-\omega(1)}$ $\mathsf{BPP}$ .

Poin utama di sini adalah bahwa dalam kita dapat secara efisien mengurangi probabilitas kesalahan secara eksponensial sehingga kita hampir pasti tentang jawabannya dan itulah yang membuat kita menganggap kelas algoritma ini sebagai algoritma yang efisien. Probabilitas kesalahan dapat dikurangi sedemikian rupa sehingga kegagalan perangkat keras lebih mungkin atau bahkan meteor yang jatuh pada komputer lebih mungkin daripada membuat kesalahan dengan algoritma probabilistik. $\mathsf{BPP}$

Itu tidak benar untuk , kita tidak tahu cara mengurangi kemungkinan kesalahan dan kita dibiarkan hampir seolah-olah kita menjawab dengan melempar koin untuk mendapatkan jawaban (kita tidak sepenuhnya, probabilitasnya adalah bukan setengah dan setengah, tetapi sangat dekat dengan situasi itu). $\mathsf{PP}$

Bagian ini memberikan bukti bahwa untuk mendapatkan probabilitas kesalahan ketika kita mulai dengan algoritma dengan gap kita harus menjalankan $\epsilon$ $(\frac{1}{2}-\delta,\frac{1}{2}+\delta)$ $M$ $\Theta(\delta^{-1} \lg \epsilon)$ kali.

Biarkan menjadi algoritma yang menjalankan untuk kali dan kemudian menjawab sesuai dengan jawaban mayoritas. Untuk kesederhanaan, mari kita asumsikan bahwa $N_k$ $M$ $k$ $k$ itu aneh sehingga kita tidak memiliki ikatan.

Pertimbangkan kasus yang . Kasus ini mirip. Kemudian Untuk menganalisis probabilitas kebenaran kita perlu memperkirakan probabilitas bahwa mayoritas yang berjalan menerima. $x \in L$ $x \notin L$

P r {M (x) accepts} = p \geq \frac{1}{2} + δ

$\mathsf{Pr}\{M(x) \text{ accepts}\} = p \geq \frac{1}{2} + \delta$

N_{k}

$N_k$

k

$k$

Mari menjadi 1 jika run th menerima dan menjadi jika menolak. Perhatikan bahwa setiap proses independen dari yang lain karena mereka menggunakan bit acak independen. Dengan demikian adalah variabel acak Boolean independen di mana $X_i$ $i$ $0$ $X_i$

E [X_{i}] = P r {X_{i} = 1} = P r {M (x) accepts} = p \geq \frac{1}{2} + δ

$\mathbb{E}[X_i] = \mathsf{Pr}\{X_i=1\} = \mathsf{Pr}\{M(x)\text{ accepts}\} = p \geq \frac{1}{2}+\delta$

Biarkan . Kita perlu memperkirakan probabilitas yang diterima mayoritas, yaitu probabilitas bahwa . $Y = \Sigma_{i=1}^k X_i$ $Y\geq\frac{k}{2}$

P r {N_{k} (x) accepts} = P r {Y \geq \frac{k}{2}}

$\mathsf{Pr}\{N_k(x) \text{ accepts}\} = \mathsf{Pr}\{Y \geq \frac{k}{2}\}$

Bagaimana cara melakukannya? Kita dapat menggunakan batas Chernoff yang memberi tahu kita konsentrasi probabilitas di dekat nilai yang diharapkan. Untuk setiap variabel acak dengan nilai yang diharapkan , kami miliki $Z$ $\mu$

P r {| Z - μ | > α μ} < e^{\frac{α^{2}}{4} μ}

$\mathsf{Pr}\{|Z-\mu| > \alpha\mu\} < e^{\frac{\alpha^2}{4}\mu}$

yang mengatakan bahwa probabilitas adalah jauh dari nilai yang diharapkan menurun secara eksponensial ketika meningkat. Kami akan menggunakannya untuk mengikat probabilitas $Z$ $\alpha\mu$ $\mu$ $\alpha$ $Y < \frac{k}{2}$ .

Perhatikan bahwa dengan linearitas harapan kita memiliki

E [Y] = E [Σ_{i = 1}^{k} X_{i}] = Σ_{i = 1}^{k} E [X_{i}] = k p \geq \frac{k}{2} + k δ

$\mathbb{E}[Y] = \mathbb{E}[\Sigma_{i=1}^k X_i] = \Sigma_{i=1}^k \mathbb{E}[X_i] = kp \geq \frac{k}{2} + k\delta$

Sekarang kita bisa menerapkan ikatan Chernoff. Kami ingin batas atas pada probabilitas . Batas Chernoff akan memberikan batas atas pada probabilitas yang cukup. Kita punya $Y< \frac{k}{2}$ $|Y-(\frac{k}{2}+k\delta)| > k\delta$

P r {| Y - k p | > α k p} < e^{- \frac{α^{2}}{4} k p}

$Pr\{|Y - kp| > \alpha kp\} < e^{-\frac{\alpha^2}{4}kp}$

dan jika kita memilih sehingga kita selesai, jadi kita memilih $\alpha$ $\alpha kp = k\delta$ $\alpha = \frac{\delta}{p} \leq \frac{2\delta}{2\delta+1}$ .

Karena itu kami punya

P r {Y < \frac{k}{2}} \leq P r {| Y - (\frac{k}{2} + k δ) | > k δ} \leq P r {| Y - k p | > α k p} < e^{- \frac{α^{2}}{4} k p}

$Pr\{Y < \frac{k}{2} \} \leq Pr\{|Y - (\frac{k}{2}+k\delta)| > k\delta\} \leq Pr\{|Y - kp| > \alpha kp\} < e^{-\frac{\alpha^2}{4}kp}$

dan jika Anda melakukan perhitungan Anda akan melihat itu

\frac{α^{2}}{4} k p \leq \frac{δ^{2}}{4 δ + 2} k = Θ (k δ)

$\frac{\alpha^2}{4}kp \leq \frac{\delta^2}{4\delta+2}k = \Theta(k\delta)$

kita punya

P r {Y < \frac{k}{2}} < e^{- Θ (k δ)}

$Pr\{Y < \frac{k}{2} \} < e^{-\Theta(k\delta)}$

Kami ingin kesalahan paling banyak , jadi kami mau $\epsilon$

e^{- Θ (k δ)} \leq ϵ

$e^{-\Theta(k\delta)} \leq \epsilon$

atau dengan kata lain

Θ (δ^{- 1} \lg ϵ) \leq k

$\Theta(\delta^{-1} \lg \epsilon) \leq k$

Satu poin penting di sini adalah bahwa dalam proses ini kita akan menggunakan lebih banyak bit acak dan juga waktu berjalan akan meningkat, yaitu waktu berjalan terburuk dari akan kira-kira kali waktu berjalan $N_k$ $k$ $M$ .

Di sini titik tengah jeda adalah . Tetapi secara umum hal ini tidak perlu terjadi. Kita dapat mengadopsi metode serupa untuk nilai-nilai lain dengan mengambil pecahan lain menggantikan mayoritas untuk menerima. $\frac{1}{2}$

Kaveh
sumber

7

Menggunakan notasi Anda:

$BPP =\{L : \exists$ mesin Turing polinomial-waktu probabilistik dan Costant sedemikian rupa sehingga $M,$ $0 < c \leq 1/2$ $\forall x \; Pr[\chi_L(x) = M(x)] \geq \frac{1}{2} + c\}$

$PP =\{L : \exists$ sebuah probabilistik polinomial-waktu Turing Machine sehingga $M$ $\forall x \; Pr[\chi_L(x) = M(x)] > \frac{1}{2}\}$

Perbedaannya telah ditunjukkan oleh adrianN, dan Anda juga dapat melihat Wikipedia PP vs BPP

Vor
sumber

Pemahaman konkret tentang perbedaan antara definisi PP dan BPP

Jawaban: