Изменения

Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>L</tex> таких, что существует программа [[Вероятностные вычисления. Вероятностная машина Тьюринга|ВМТ]] <tex>pm</tex>, которая работает за полиномиальное время что для любой вероятностной ленты, илюбого <tex>x</tex>:# <tex>x \notin L \Rightarrow P(pm(x) = 0) = 1</tex>;# <tex>x \in L \Rightarrow P(pm(x) = 1) \geq \frac{1}{2}</tex>;# <tex>T(m(x, r)) \le poly(|x|)</tex> для любой вероятностной ленты <tex>r</tex>.

Сложностный класс <tex>\mathrm{RP_{weak}}</tex> состоит из языков <tex>L</tex> таких, что существует программа ВМТ <tex>pm</tex>, которая работает за полиномиальное время что для любой вероятностной ленты, илюбого <tex>x</tex>:# <tex>x \notin L \Rightarrow P(pm(x) = 0) = 1</tex>;# <tex>x \in L \Rightarrow P(pm(x) = 1) \geq \frac{1}{q(|x|)}</tex>, где <tex>q(|x|)</tex> — некоторый полином, <tex>q(|x|) \geq 1</tex>;# <tex>T(m(x, r)) \le poly(|x|)</tex> для любой вероятностной ленты <tex>r</tex>.

Сложностный класс <tex>\mathrm{RP_{strong}}</tex> состоит из языков <tex>L</tex> таких, что существует программа ВМТ <tex>pm</tex>, которая работает за полиномиальное время что для любой вероятностной ленты, илюбого <tex>x</tex>:# <tex>x \notin L \Rightarrow P(pm(x) = 0) = 1</tex>;# <tex>x \in L \Rightarrow P(pm(x) = 1) \geq 1 - \frac{1}{2^{q(|x|)}}</tex>, где <tex>q(|x|)</tex> — некоторый полином;# <tex>T(m(x, r)) \le poly(|x|)</tex> для любой вероятностной ленты <tex>r</tex>.