205
правок
Изменения
Новая страница: «== Определения == {{Определение |definition= Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>...»
== Определения ==
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP}</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}</tex>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{weak}}</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}{q(|x|)}</tex>, где <tex>q</tex> — некоторый полином.
}}
{{Определение
|definition=
Сложностный класс <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> — некоторый полином.
}}
{{Теорема
|statement=<tex>\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}</tex>
|proof=
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP}</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}</tex>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{weak}}</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}{q(|x|)}</tex>, где <tex>q</tex> — некоторый полином.
}}
{{Определение
|definition=
Сложностный класс <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> — некоторый полином.
}}
{{Теорема
|statement=<tex>\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}</tex>
|proof=
}}
