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.

Диаграмма «ближайших» классов[править]

Graph image creation requires permission to upload.

Ссылки[править]


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