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

c o R P { L | L R P } co{\cal RP} \equiv \{L|\overline{L} \in {\cal RP}\}

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

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

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

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

G P P ZPP ZPP P->ZPP in NP NP PP PP NP->PP in coNP coNP coNP->PP in BPP BPP ZPP->BPP in RP RP ZPP->RP in coRP coRP ZPP->coRP in BPP->PP in RP->NP in RP->BPP in coRP->coNP in coRP->BPP in PCP(poly,0) PCP(poly,0) coRP->PCP(poly,0) equal


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