Классы RP и coRP — различия между версиями
м (→Определения) |
м |
||
| Строка 10: | Строка 10: | ||
Сложностный класс <tex>\mathrm{RP_{weak}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</tex>, которая работает за полиномиальное время, и: | Сложностный класс <tex>\mathrm{RP_{weak}}</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}{q(|x|)}</tex>, где <tex>q</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>. |
}} | }} | ||
{{Определение | {{Определение | ||
| Строка 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 1 - \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(|x|)</tex> — некоторый полином, <tex>q(|x|) \geq 1</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_{strong}} \subset \mathrm{RP}\colon</tex> | ||
}} | }} | ||
| + | == См. также == | ||
| + | *[[Вероятностные вычисления. Вероятностная машина Тьюринга]] | ||
Версия 18:20, 23 мая 2012
Определения
| Определение: |
Сложностный класс состоит из языков таких, что существует программа , которая работает за полиномиальное время, и:
|
| Определение: |
Сложностный класс состоит из языков таких, что существует программа , которая работает за полиномиальное время, и:
|
| Определение: |
Сложностный класс состоит из языков таких, что существует программа , которая работает за полиномиальное время, и:
|
Теорема об эквивалентности определений
| Теорема: |
| Доказательство: |
