Классы BPP

Определения

Определение:

[math]\mathrm{BPP_{weak}}[/math] — класс языков [math]L[/math], для которых существует [math]p[/math], такая, что для любого [math]x[/math]: [math]P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(|x|)}[/math], где [math]q[/math]-полином и [math]q(|x|) \ge 3[/math]; [math]T(p(x)) \le poly(|x|)[/math] для любой вероятностной ленты.

Определение:

[math]\mathrm{BPP_{strong}}[/math] — класс языков [math]L[/math], для которых существует [math]p[/math], такая, что для любого [math]x[/math]: [math]P(p(x)=[x \in L]) \ge 1 - 1 / {2^{q(|x|)}}[/math], где [math]q[/math]-полином и [math]q(|x|) \ge 3[/math]; [math]T(p(x)) \le poly(|x|)[/math] для любой вероятностной ленты.

Теорема

Теорема:

[math]BPP = BPP_{weak} = BPP_{strong}[/math]

Доказательство:

[math]\triangleright[/math]

Для доказательства теоремы будем использовать неравенство Чернова: [math]\forall p \ge \frac {1} {2} : \sum\limits_{i = \lfloor \frac{n}{2} \rfloor + 1}^n \binom{n}{i}p^i (1 - p)^{n - i} \ge 1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2}[/math] Докажем, что [math]BPP = BPP_{weak}[/math] [math]BPP \subseteq BPP_{weak}[/math] Это понятно из определений [math]BPP[/math] и [math]BPP_{weak}[/math]. [math]BPP_{weak} \subseteq BPP[/math] Пусть [math]L \in BPP_{weak}[/math]. Тогда [math]\exists p : P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(|x|)}[/math]. Построим ВМТ [math]p_1[/math], которая для входа [math]x[/math] запускает [math]p(x)[/math] [math]n[/math] раз, и, если больше половины запусков принимают [math]x[/math], то [math]p_1[/math] принимает [math]x[/math]. Подберем [math]n[/math], такое, что [math]P(p_1(x)=[x \in L]) \ge \frac {2}{3}[/math] и [math]T(p_1(x)) \le poly(|x|)[/math]. Вероятность [math]P[/math] того, что [math]p_1(x)[/math] даст правильный результат равна вероятности, что больше половины запусков [math]p(x)[/math] дадут правильный результат. Тогда по схеме Бернулли [math]P = \sum\limits_{i = \lfloor \frac{n}{2} \rfloor + 1}^n \binom{n}{i}p^i (1 - p)^{n - i}[/math], где [math]p=\frac {1}{2} + \frac {1} {q(|x|)}[/math] — вероятность, что запуск [math]p(x)[/math] даст правильный ответ. По неравенству Чернова [math] P \ge 1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} [/math]. То есть для того, чтобы [math]P(p(x)=[x \in L]) \ge \frac {2}{3}[/math] достаточно подобрать [math]n[/math], такое что [math]1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} \ge \frac {2}{3}[/math]. Получаем, что [math]n \ge \frac {\ln 3} {2(p - \frac {1} {2})^2} = \frac {{q(|x|)}^2 \ln 3}{2} [/math]. Следовательно, мы можем взять [math]n[/math] такое, что [math]T(p_1(x)) \le poly(|x|)[/math] Докажем, что [math]BPP = BPP_{strong}[/math] [math]BPP_{strong} \subseteq BPP [/math] Это понятно из определений [math]BPP[/math] и [math]BPP_{strong}[/math]. [math]BPP \subseteq BPP_{strong}[/math] Пусть [math]L \in BPP[/math]. Тогда [math]\exists p : P(p(x)=[x \in L]) \ge \frac {2}{3}[/math]. Построим ВМТ [math]p_1[/math], которая для входа [math]x[/math] запускает [math]p(x)[/math] [math]n[/math] раз, и, если больше половины запусков принимают [math]x[/math], то [math]p_1[/math] принимает [math]x[/math]. Подберем [math]n[/math], такое, что [math]P(p_1(x)=[x \in L]) \ge 1 - \frac {1}{2^{q(|x|)}}[/math] и [math]T(p_1(x)) \le poly(|x|)[/math]. Проводя рассуждения аналогичные изложенным в доказательстве [math]BPP_{weak} \subseteq BPP[/math], получаем, что [math]1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} \ge 1 - \frac {1}{2^{q(|x|)}}[/math]. Отсюда [math]n \ge \frac {{q(|x|)} \ln 2}{2({\frac {2}{3} - \frac {1}{2}})^2} [/math]. Следовательно, мы можем взять [math]n[/math] такое, что [math]T(p_1(x)) \le poly(|x|)[/math]

[math]\triangleleft[/math]

См. также

• Вероятностные вычисления. Вероятностная машина Тьюринга