Конкретное понимание различий между определениями PP и BPP

9

Я не совсем понимаю, как определяются PP и BPP . Пусть характеристическая функция для языка . М - вероятностная машина Тьюринга. Верны ли следующие определения: $\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} \}$

Если определение неверно, пожалуйста, попробуйте внести минимальные изменения, чтобы сделать их правильными (т.е. не давать другого эквивалентного определения, которое использует счетную машину или некоторую модифицированную модель). Я не могу правильно различить условия вероятности по обоим определениям.

Некоторые конкретные примеры с четким пониманием тонких моментов были бы очень полезны.

complexity-theory terminology randomized-algorithms complexity-classes DurgaDatta
источник

10

Это выглядит правильно для меня. Разница между БПП и ПП является то , что для БПП вероятность того, должна быть больше , чем константой , тогда как для PP это может быть . Таким образом, для проблем BPP вы можете сделать усиление вероятности с небольшим количеством повторений, тогда как для общих проблем PP вы не можете. $1/2$ $1/2+ 1/2^n$

adrianN
источник

12

Ответ Вора дает стандартное определение. Позвольте мне попытаться объяснить разницу немного более интуитивно.

Пусть - вероятностный алгоритм с полиномиальным временем с ограниченной ошибкой для языка который правильно отвечает с вероятностью не менее $M$ $L$ . Пустьбудет входом, а- размером ввода. $p\geq\frac{1}{2}+\delta$ $x$ $n$

Что отличает произвольный алгоритм из алгоритма является положительным разрывом между вероятностью приема и вероятностью принятия . $\mathsf{PP}$ $\mathsf{BPP}$ $x\in L$ $x\notin L$ Существенным моментом в является то, что зазор составляет не менее . Я попытаюсь объяснить, почему это различие является значительным и позволяет нам рассматривать как эффективные алгоритмы (даже предполагаемые равными $\mathsf{BPP}$ $n^{-O(1)}$ $\mathsf{BPP}$ $\mathsf{P}$ ) тогда как считается неэффективным (фактически содержит ). Все это происходит из этого разрыва. $\mathsf{PP}$ $\mathsf{PP}$ $\mathsf{NP}$

Давайте начнем с рассмотрения более внимательно. $\mathsf{PP}$

Обратите внимание, что если алгоритм использует не более случайных битов во время своего выполнения, а вероятность ошибки меньше, чем тогда вероятность ошибки фактически равна , не может быть никакого выбора случайных битов, которые сделают алгоритм ответить неправильно. $r(n)$ $2^{-r(n)}$ $0$

Кроме того, алгоритм с временем выполнения не может использовать более случайных битов, поэтому, если ошибка вероятностного алгоритма с наихудшим временем выполнения лучше, чем $t(n)$ $t(n)$ $t(n)$

С помощью аналогичного аргумента мы можем показать, что случай, когда разница между вероятностью принятия и вероятностью принятия слишком мала, аналогичен случаю, когда у нас почти нет разницы, как в чехол. $x\in L$ $x\notin L$ $\mathsf{PP}$

Теперь давайте двигаться в направлении . $\mathsf{BPP}$

В вероятностных алгоритмах мы можем повысить вероятность правильного ответа. Допустим, мы хотим повысить вероятность правильности до для, например, вероятности ошибки (экспоненциально малая ошибка). $1-\epsilon$ $\epsilon=2^{-n}$

Идея проста: запустить несколько раз и принять ответ большинства. $M$

Сколько раз мы должны запустить чтобы получить вероятность ошибки не более ? раз. Доказательство приводится внизу этого ответа. $M$ $\epsilon$ $\Theta(\delta^{-1} \lg \epsilon)$

Теперь давайте примем во внимание, что алгоритмы, которые мы обсуждаем, должны быть полиномиального времени. Это означает, что мы не можем запустить больше, чем полиномиально много раз. Другими словами, или проще $M$ $\Theta(\delta^{-1} \ln \epsilon) = n^{O(1)}$

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

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

Это отношение классифицирует вероятностные алгоритмы с ограниченной ошибкой на классы в зависимости от их вероятности ошибки. Там нет никакой разницы между вероятностью ошибки быть быть или положительная константа (т.е. не изменяется с ) или $\epsilon$ $2^{-n}$ $n$ . Мы можем перейти от одного к другому, оставаясь внутри полиномиального времени. $\frac{1}{2}-n^{O(1)}$

Однако , если слишком мал, скажем , , , или даже , то мы не имеем способ повышения корректности вероятности и снижения вероятности ошибки достаточно , чтобы попасть в . $\delta$ $0$ $2^{-n}$ $n^{-\omega(1)}$ $\mathsf{BPP}$

Главное здесь то, что в мы можем эффективно уменьшить вероятность ошибки по экспоненте, поэтому мы почти уверены в ответах, и именно это заставляет нас рассматривать этот класс алгоритмов как эффективные алгоритмы. Вероятность ошибки может быть уменьшена настолько, что аппаратный сбой более вероятен, или даже метеорит, падающий на компьютер, более вероятен, чем ошибка с помощью вероятностного алгоритма. $\mathsf{BPP}$

Это не верно для , мы не знаем никакого способа уменьшения вероятности ошибки, и у нас остается почти так, как будто мы отвечаем, бросая монетку, чтобы получить ответ (мы не полностью, вероятности не являются половиной и половина, но это очень близко к этой ситуации). $\mathsf{PP}$

$\epsilon$ $(\frac{1}{2}-\delta,\frac{1}{2}+\delta)$ $M$ $\Theta(\delta^{-1} \lg \epsilon)$

$N_k$ $M$ $k$ $k$

$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$

$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$

$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}\}$

$Z$ $\mu$

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

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

$Z$ $\alpha\mu$ $\mu$ $\alpha$ $Y < \frac{k}{2}$

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$

$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}$

$\alpha$ $\alpha kp = k\delta$ $\alpha = \frac{\delta}{p} \leq \frac{2\delta}{2\delta+1}$

Поэтому мы имеем

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}$

и если вы сделаете расчеты, вы увидите, что

\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)$

у нас есть

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

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

$\epsilon$

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

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

или другими словами

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

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

$N_k$ $k$ $M$

$\frac{1}{2}$

Кава
источник

7

Используя вашу запись:

$BPP =\{L : \exists$ $M,$ $0 < c \leq 1/2$ $\forall x \; Pr[\chi_L(x) = M(x)] \geq \frac{1}{2} + c\}$

$PP =\{L : \exists$ $M$ $\forall x \; Pr[\chi_L(x) = M(x)] > \frac{1}{2}\}$

AdrianN указал на разницу, и вы также можете взглянуть на Википедию PP против BPP

Вор
источник

Конкретное понимание различий между определениями PP и BPP

Ответы: