Классы BPP

Определения

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

[math]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]T(p(x)) \le poly(|x|)[/math] для любой вероятностной ленты.

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

[math]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]T(p(x)) \le poly(|x|)[/math] для любой вероятностной ленты.