Классы RP и coRP — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Определения == {{Определение |definition= Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>...»)
 
м (Определения)
Строка 16: Строка 16:
 
Сложностный класс <tex>\mathrm{RP_{strong}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</tex>, которая работает за полиномиальное время, и:
 
Сложностный класс <tex>\mathrm{RP_{strong}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</tex>, которая работает за полиномиальное время, и:
 
# <tex>x \notin L \Rightarrow P(m(x) = 0) = 1</tex>;
 
# <tex>x \notin L \Rightarrow P(m(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(m(x) = 1) \geq \frac{1}{2^{q(|x|)}}</tex>, где <tex>q</tex> — некоторый полином.
+
# <tex>x \in L \Rightarrow P(m(x) = 1) \geq 1 - \frac{1}{2^{q(|x|)}}</tex>, где <tex>q</tex> — некоторый полином.
 
}}
 
}}
 
{{Теорема
 
{{Теорема

Версия 17:46, 23 мая 2012

Определения

Определение:
Сложностный класс [math]\mathrm{RP}[/math] состоит из языков [math]L[/math] таких, что существует программа [math]m[/math], которая работает за полиномиальное время, и:
  1. [math]x \notin L \Rightarrow P(m(x) = 0) = 1[/math];
  2. [math]x \in L \Rightarrow P(m(x) = 1) \geq \frac{1}{2}[/math].


Определение:
Сложностный класс [math]\mathrm{RP_{weak}}[/math] состоит из языков [math]L[/math] таких, что существует программа [math]m[/math], которая работает за полиномиальное время, и:
  1. [math]x \notin L \Rightarrow P(m(x) = 0) = 1[/math];
  2. [math]x \in L \Rightarrow P(m(x) = 1) \geq \frac{1}{q(|x|)}[/math], где [math]q[/math] — некоторый полином.


Определение:
Сложностный класс [math]\mathrm{RP_{strong}}[/math] состоит из языков [math]L[/math] таких, что существует программа [math]m[/math], которая работает за полиномиальное время, и:
  1. [math]x \notin L \Rightarrow P(m(x) = 0) = 1[/math];
  2. [math]x \in L \Rightarrow P(m(x) = 1) \geq 1 - \frac{1}{2^{q(|x|)}}[/math], где [math]q[/math] — некоторый полином.
Теорема:
[math]\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}[/math]