Изменения
Новая страница: «==Определения== {{Определение |definition= <tex>BPP_{weak}</tex> — множество языков <tex>L</tex>, для которых с...»
==Определения==
{{Определение
|definition=
<tex>BPP_{weak}</tex> — множество языков <tex>L</tex>, для которых существует <tex>p</tex>, такая, что для любого <tex>x</tex>:
#<tex>P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(|x|)}</tex>, где <tex>q</tex>-полином;
#<tex>T(p(x)) \le poly(|x|)</tex> для любой вероятностной ленты.
}}
{{Определение
|definition=
<tex>BPP_{strong}</tex> — множество языков <tex>L</tex>, для которых существует <tex>p</tex>, такая, что для любого <tex>x</tex>:
#<tex>P(p(x)=[x \in L]) \ge 1 - 1 / {2^{q(|x|)}}</tex>, где <tex>q</tex>-полином;
#<tex>T(p(x)) \le poly(|x|)</tex> для любой вероятностной ленты.
}}
{{Определение
|definition=
<tex>BPP_{weak}</tex> — множество языков <tex>L</tex>, для которых существует <tex>p</tex>, такая, что для любого <tex>x</tex>:
#<tex>P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(|x|)}</tex>, где <tex>q</tex>-полином;
#<tex>T(p(x)) \le poly(|x|)</tex> для любой вероятностной ленты.
}}
{{Определение
|definition=
<tex>BPP_{strong}</tex> — множество языков <tex>L</tex>, для которых существует <tex>p</tex>, такая, что для любого <tex>x</tex>:
#<tex>P(p(x)=[x \in L]) \ge 1 - 1 / {2^{q(|x|)}}</tex>, где <tex>q</tex>-полином;
#<tex>T(p(x)) \le poly(|x|)</tex> для любой вероятностной ленты.
}}
