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