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

coRP{L|LRP}co{\cal RP} \equiv \{L|\overline{L} \in {\cal RP}\}

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

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

xLP[M(x)=0]12x \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.Список авторов доступен на этом ресурсе в статье под тем же названием.