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

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

Определение:

Сложностный класс состоит из языков таких, что существует программа , которая работает за полиномиальное время, и:

Определение:

Сложностный класс состоит из языков таких, что существует программа , которая работает за полиномиальное время, и:

Определение:

Сложностный класс состоит из языков таких, что существует программа , которая работает за полиномиальное время, и:

Теорема:

@@ Строка 16: / Строка 16: @@
 Сложностный класс <tex>\mathrm{RP_{strong}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</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> — некоторый полином.
 }}
 {{Теорема