Определения
[math]BPP = \{L |{ }\exist m: T(m,x) = Poly(|x|) \and P(m(x) = [x \in L]) \gt 2/3\}[/math]
где [math]m[/math] -- вероятностная машина Тьюринга.
Существуют альтернативные определения класса [math]BPP[/math]:
- [math]BPP_{weak} = \{L |{ }\exist m: T(m,x) = Poly(|x|) \and P(m(x) = [x \in L]) \gt 1/2 + 1/p(|x|)\}[/math]
где [math]m[/math] -- ВМТ, а [math]~p(|x|): \forall x: p(|x|) \gt 2[/math] -- полином.
- [math]BPP_{strong} = \{L |{ }\exist m: T(m,x) = Poly(|x|) \and P(m(x) = [x \in L]) \gt 1 - 2^{-p(|x|)}\}[/math]
где [math]m[/math] -- ВМТ, а [math]~p(|x|)[/math] -- полином.
Эквивалентность определений
Требуется доказать, что [math]~BPP_{strong} = BPP= BPP_{weak}[/math].
Для доказательства обоих равенств потребуется неравенство Чернова:
[math]\sum_{\mathcal{b}\frac{n}{2}\mathcal{c}+1}^{n}[{{{n\choose i}} p^{i}(1-p)^{n-i}] \geq 1 - e^{-2n(p-1/2)^2}}[/math]
Доказательство [math]~BPP_{strong} = BPP[/math]
Очевидно, что [math]~BPP_{strong} \subset BPP[/math].
Докажем обратное включение. Пусть [math]L \in BPP[/math], тогда существует
ВМТ [math]m_{1}: T(m_{1},x) = Poly(|x|) \and P(m_{1}(x) = [x \in L]) \gt 2/3[/math]. Построим ВМТ [math]m_{2}: T(m_{2},x) = Poly(|x|) \and P(m_{2}(x) = [x \in L]) \gt 1 - 2^{-p(|x|)}[/math],
используя заданные [math]m_{1}[/math] и [math]~p(|x|)[/math]. Если нам это удастся, то [math]L \in BPP_{strong} \Rightarrow BPP \in BPP_{strong} \Rightarrow ~BPP_{strong} = BPP[/math].
Построение [math]m_{2}[/math]
Доказательство [math]~BPP_{weak} = BPP[/math]
Очевидно, что [math]~BPP \subset BPP_{weak}[/math].
Докажем обратное включение. Пусть [math]L \in BPP_{weak}[/math], тогда существует
ВМТ [math]m_{1}: T(m_{1},x) = Poly(|x|) \and P(m_{1}(x) = [x \in L]) \gt 1/2 + 1/p(|x|)[/math]. Построим ВМТ [math]m_{2}: T(m_{2},x) = Poly(|x|) \and P(m_{2}(x) = [x \in L]) \gt 2/3[/math],
используя заданные [math]m_{1}[/math] и [math]~p(|x|)[/math]. Если нам это удастся, то [math]L \in BPP \Rightarrow BPP_{weak} \in BPP \Rightarrow ~BPP_{weak} = BPP[/math].
Построение [math]m_{2}[/math]
