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.

Ссылки

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