322
правки
Изменения
Нет описания правки
# <tex>T(m(x, r)) \le poly(|x|)</tex> для любой вероятностной ленты <tex>r</tex>.
}}
<tex>\mathrm{RP}</tex> — сложностный класс, допускающий ошибки программ на словах из <tex>L</tex>.
Заметим, что константа <tex>1/2</tex> в пункте 2 определения <tex>\mathrm{RP}</tex> может быть заменена на любую другую из промежутка <tex>(0, 1)</tex>, поскольку требуемой вероятности можно добиться множественным запуском программы.
<tex>\mathrm{RP}</tex> можно рассматривать как вероятностный аналог класса <tex>\mathrm{NP}</tex>, предполагая, что вероятность угадать сертификат в случае его существования не менее <tex>1/2</tex>.
{{Определение
|definition =
<tex>\mathrm{coRP} = \{L \bigm| \overline L \in \mathrm{RP}\}</tex>.
}}
Класс <tex>\mathrm{coRP}</tex> допускает ошибки программ на словах, не принадлежащих <tex>L</tex>.
{{Определение
|definition=
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство<br/><tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>.<br/> Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
}}
== Теорема о соотношении классов <tex>\mathrm{coRP}</tex> и <tex>\Pi_1</tex> Литература =={{Теорема|statement = <tex>\mathrm{coRP} \subset \Pi_1<* S.Arora, B.Barak. Randomized computation. Cambridge University, January 2007. [http://tex>www.|proof = <tex>L \in \mathrm{coRP} \Leftrightarrow \overline{L} \in \mathrm{RP} \Rightarrow \overline{L} \in \mathrm{NP} \Leftrightarrow L \in \mathrm{coNP} = \Pi_1<cs.princeton.edu/theory/complexity/tex>bppchap.pdf]}}
== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
