RP

Класс сложности RP (Random Polynomial-time) состоит из всех языков L для которых существует полиномиальная вероятностная машина Тьюринга M, такая что:

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

• $x \notin L \Rightarrow P[M(x)=0]=1$

Константа 1/2 выбрана произвольно. Её можно заменить любой другой константой большей 0 и меньшей 1. При этом RP будет содержать те же задачи, но языки, определяемые конкретными вероятностными машинами Тьюринга, изменятся.

Можно, пользуясь тем, что в в «offline»-определении ВМТ подразумевается отделенность вероятностных данных от обычной ДМТ, дать альтернативное определение, заменив вероятности, на доли строк-сертификатов:

Варианты определения

Определение через Детерминированную Машину Тьюринга

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

• $x \in L \Rightarrow \frac{|\{y:M(x,y)=1,|y|\leq p(|x|)\}|}{2^{p(|x|)}}\geq \frac{1}{2}$

• $x \notin L \Rightarrow \forall y, M(x,y)=0$

Можно показать, что будут эквивалентны также следующие определения класса RP:

«Строгое» определение

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

• $x \in L \Rightarrow P[M(x)=1]\geq 1 - 2^{-p(|x|)}$
• $x \notin L \Rightarrow P[M(x)=1]=0$

«Свободное» определение

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

• $x \in L \Rightarrow P[M(x)=1]\geq \frac{1}{p(|x|)}$
• $x \notin L \Rightarrow P[M(x)=1]=0$

Аналогичные определения можно дать и для класса coRP.

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

Ссылки

• RP в custiswiki
• Курс Н. П. Варновского Понятия теории сложности вычислений

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