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}\)

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

Graph image creation requires permission to upload.


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