CoRP

CoRP — класс-дополнение к классу RP. Можно определить, как

$co{\cal RP} \equiv \{L|\overline{L} \in {\cal RP}\}$

или как класс сложности, который состоит из всех языков L для которых существует полиномиальная вероятностная машина Тьюринга M, такая что:

$x \in L \Rightarrow P[M(x)=1] =1$

$x \notin L \Rightarrow P[M(x)=0] \geq\frac{1}{2}$

Диаграмма «ближайших» классов сложности

По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.