Классы RP и coRP

Определения

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

Сложностный класс [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]L \in \mathrm{RP_{strong}}[/math]. Этому языку соответсвует программа [math]m_{\mathrm{RP_{strong}}}[/math]. Для доказательства утверждения необходимо написать программу [math]m_{\mathrm{RP}}[/math], которая будет удолетворять ограничениям сложностного класса [math]\mathrm{RP}[/math]. В качестве программы [math]m_{\mathrm{RP}}[/math] можно взять программу [math]m_{\mathrm{RP_{strong}}}[/math], так как [math]1 - \frac{1}{2^p} \geq \frac{1}{2} \Leftrightarrow p \geq 1[/math]. То есть программа [math]m_{\mathrm{RP_{strong}}}[/math] удолетворяет ограничениям сложностного класса [math]\mathrm{RP}[/math].

[math]\triangleleft[/math]

См. также

• Вероятностные вычисления. Вероятностная машина Тьюринга