Редактирование: Классы RP и coRP

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 2: Строка 2:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>L</tex> таких, что существует [[Вероятностные вычисления. Вероятностная машина Тьюринга|ВМТ]] <tex>m</tex> такая, что для любого <tex>x</tex>:
+
Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>p</tex>, которая работает за полиномиальное время для любой вероятностной ленты, и:
# <tex>x \notin L \Rightarrow P(m(x) = 0) = 1</tex>;
+
# <tex>x \notin L \Rightarrow P(p(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(m(x) = 1) \geq \frac{1}{2}</tex>;
+
# <tex>x \in L \Rightarrow P(p(x) = 1) \geq \frac{1}{2}</tex>.
# <tex>T(m(x, r)) \le poly(|x|)</tex> для любой вероятностной ленты <tex>r</tex>.
 
 
}}
 
}}
<tex>\mathrm{RP}</tex> — сложностный класс, допускающий ошибки программ на словах из <tex>L</tex>.
 
Заметим, что константа <tex>1/2</tex> в пункте 2 определения <tex>\mathrm{RP}</tex> может быть заменена на любую другую из промежутка <tex>(0, 1)</tex>, поскольку требуемой вероятности можно добиться множественным запуском программы.
 
 
<tex>\mathrm{RP}</tex> можно рассматривать как вероятностный аналог класса <tex>\mathrm{NP}</tex>, предполагая, что вероятность угадать сертификат в случае его существования не менее <tex>1/2</tex>.
 
 
{{Определение
 
|definition =
 
<tex>\mathrm{coRP} = \{L \bigm| \overline L \in \mathrm{RP}\}</tex>.
 
}}
 
Класс <tex>\mathrm{coRP}</tex> допускает ошибки программ на словах, не принадлежащих <tex>L</tex>.
 
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Сложностный класс <tex>\mathrm{RP_{weak}}</tex> состоит из языков <tex>L</tex> таких, что существует ВМТ <tex>m</tex> такая, что для любого <tex>x</tex>:
+
Сложностный класс <tex>\mathrm{RP_{weak}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>p</tex>, которая работает за полиномиальное время для любой вероятностной ленты, и:
# <tex>x \notin L \Rightarrow P(m(x) = 0) = 1</tex>;
+
# <tex>x \notin L \Rightarrow P(p(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(m(x) = 1) \geq \frac{1}{q(|x|)}</tex>, где <tex>q(|x|)</tex> — некоторый полином, <tex>q(|x|) \geq 1</tex>;
+
# <tex>x \in L \Rightarrow P(p(x) = 1) \geq \frac{1}{q(|x|)}</tex>, где <tex>q(|x|)</tex> — некоторый полином, <tex>q(|x|) \geq 1</tex>.
# <tex>T(m(x, r)) \le poly(|x|)</tex> для любой вероятностной ленты <tex>r</tex>.
 
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Сложностный класс <tex>\mathrm{RP_{strong}}</tex> состоит из языков <tex>L</tex> таких, что существует ВМТ <tex>m</tex> такая, что для любого <tex>x</tex>:
+
Сложностный класс <tex>\mathrm{RP_{strong}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>p</tex>, которая работает за полиномиальное время для любой вероятностной ленты, и:
# <tex>x \notin L \Rightarrow P(m(x) = 0) = 1</tex>;
+
# <tex>x \notin L \Rightarrow P(p(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(m(x) = 1) \geq 1 - \frac{1}{2^{q(|x|)}}</tex>, где <tex>q(|x|)</tex> — некоторый полином;
+
# <tex>x \in L \Rightarrow P(p(x) = 1) \geq 1 - \frac{1}{2^{q(|x|)}}</tex>, где <tex>q(|x|)</tex> — некоторый полином.
# <tex>T(m(x, r)) \le poly(|x|)</tex> для любой вероятностной ленты <tex>r</tex>.
 
 
}}
 
}}
  
 
== Теорема об эквивалентности определений ==
 
== Теорема об эквивалентности определений ==
 
{{Теорема
 
{{Теорема
|statement=<tex>\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}</tex>.
+
|statement=<tex>\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}</tex>
 
|proof=
 
|proof=
 
<tex>\mathrm{RP_{weak}} \subset \mathrm{RP}\colon</tex><br/>
 
<tex>\mathrm{RP_{weak}} \subset \mathrm{RP}\colon</tex><br/>
Строка 74: Строка 60:
 
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство<br/><tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>.<br/> Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
 
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство<br/><tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>.<br/> Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
 
}}
 
}}
 
== Литература ==
 
* S.Arora, B.Barak. Randomized computation. Cambridge University, January 2007. [http://www.cs.princeton.edu/theory/complexity/bppchap.pdf]
 
  
 
== См. также ==
 
== См. также ==
 
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
 
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: