Классы RP и coRP

Определения

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

Сложностный класс [math]\mathrm{RP}[/math] состоит из языков [math]L[/math] таких, что существует ВМТ [math]m[/math] такая, что для любого [math]x[/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]T(m(x, r)) \le poly(|x|)[/math] для любой вероятностной ленты [math]r[/math].

[math]\mathrm{RP}[/math] — сложностный класс, допускающий ошибки программ на словах из [math]L[/math]. Заметим, что константа [math]1/2[/math] в пункте 2 определения [math]\mathrm{RP}[/math] может быть заменена на любую другую из промежутка [math](0, 1)[/math], поскольку требуемой вероятности можно добиться множественным запуском программы.

[math]\mathrm{RP}[/math] можно рассматривать как вероятностный аналог класса [math]\mathrm{NP}[/math], предполагая, что вероятность угадать сертификат в случае его существования не менее [math]1/2[/math].

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

[math]\mathrm{coRP} = \{L \bigm| \overline L \in \mathrm{RP}\}[/math].

Класс [math]\mathrm{coRP}[/math] допускает ошибки программ на словах, не принадлежащих [math]L[/math].

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

Сложностный класс [math]\mathrm{RP_{weak}}[/math] состоит из языков [math]L[/math] таких, что существует ВМТ [math]m[/math] такая, что для любого [math]x[/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]T(m(x, r)) \le poly(|x|)[/math] для любой вероятностной ленты [math]r[/math].

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

Сложностный класс [math]\mathrm{RP_{strong}}[/math] состоит из языков [math]L[/math] таких, что существует ВМТ [math]m[/math] такая, что для любого [math]x[/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]T(m(x, r)) \le poly(|x|)[/math] для любой вероятностной ленты [math]r[/math].

Теорема об эквивалентности определений

Теорема:

[math]\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}[/math].

Доказательство:

[math]\triangleright[/math]

[math]\mathrm{RP_{weak}} \subset \mathrm{RP}\colon[/math] Рассмотрим язык [math]L \in \mathrm{RP_{weak}}[/math]. Этому языку соответсвует программа [math]p_{\mathrm{RP_{weak}}}[/math]. Для доказательства утверждения необходимо написать программу [math]p_{\mathrm{RP}}[/math], которая будет удолетворять ограничениям сложностного класса [math]\mathrm{RP}[/math]. [math]p_{\mathrm{RP}}(x)[/math] for [math]i = 1 \ldots k[/math] // [math]k[/math] будет определено позже if [math]p_{\mathrm{RP_{weak}}}(x)[/math] return [math]1[/math] return [math]0[/math] Если слово [math]x \notin L[/math], то [math]p_{\mathrm{RP_{weak}}}(x)[/math] всегда возвращает [math]0[/math]. Тогда [math]P(p_{\mathrm{RP}}(x) = 0) = 1[/math], при [math]x \notin L[/math]. Если хотя бы один вызов программы [math]p_{\mathrm{RP_{weak}}}(x)[/math] вернёт [math]1[/math], то слово [math]x \in L[/math]. Вероятность ошибки программы [math]p_{\mathrm{RP_{weak}}}[/math] меньше, чем [math]1-\frac{1}{q(|x|)}[/math], то есть вероятность ошибки программы [math]p_{\mathrm{RP}}[/math] меньше, чем [math](1-\frac{1}{q(|x|)})^k[/math]. [math]k[/math] надо выбрать таким, что вероятность ошибки программы [math]m_{\mathrm{RP}}[/math] при [math]x \in L[/math] была меньше [math]\frac {1}{2}[/math]. Получается неравенство [math](1-\frac{1}{q(|x|)})^k \lt \frac{1}{2}[/math]. Логарифмируя, получаем [math]k\ ln(1-\frac{1}{q(|x|)}) \lt ln(\frac{1}{2})[/math]. Разложив логарифм в ряд Тейлора, получаем [math]k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) \lt -ln(2)[/math]. Отсюда [math]k \gt q(|x|)ln(2)[/math]. [math]\mathrm{RP} \subset \mathrm{RP_{weak}}\colon[/math] Доказательство аналогично предыдущему пункту. [math]p_{\mathrm{RP_{weak}}}(x)[/math] for [math]i = 1 \ldots k[/math] // [math]k[/math] будет определено позже if [math]p_{\mathrm{RP}}(x)[/math] return [math]1[/math] return [math]0[/math] Но здесь [math]k[/math] выбирается так, чтобы выполнялось неравенство [math](\frac{1}{2})^k \lt \frac{1}{q(|x|)}[/math]. То есть [math]k \gt log_2(q(|x|))[/math]. [math]\mathrm{RP} \subset \mathrm{RP_{strong}}\colon[/math] Напишем программу [math]p_{\mathrm{RP_{strong}}}[/math], удолетворяющую ограничениям сложностного класса [math]\mathrm{RP_{strong}}[/math]. [math]p_{\mathrm{RP_{strong}}}(x)[/math] for [math]i = 1 \ldots k[/math] // [math]k[/math] будет определено позже if [math]p_{\mathrm{RP}}(x)[/math] return [math]1[/math] return [math]0[/math] В этом случае [math]k[/math] необходимо выбрать таким, что должно выполняться неравенство [math](\frac{1}{2})^k \lt 1 - \frac{1}{2^{q(|x|)}}[/math]. То есть [math]k \gt -log_{2}(1-\frac{1}{2^{q(|x|)}})[/math]. Разложив в ряд Тейлора получаем, что [math]-log_{2}(1-\frac{1}{2^{q(|x|)}}) = \frac{2^{-q(|x|)}}{ln(2)} + o(2^{-q(|x|)}) = \frac{(1+q(|x|)+o(q(|x|)))^{ln(\frac{1}{2})}}{ln(2)} \lt \frac{1+q(|x|)}{ln(2)}[/math]. То есть [math]k[/math] надо взять больше, чем [math]\frac{1+q(|x|)}{ln(2)}[/math]. [math]\mathrm{RP_{strong}} \subset \mathrm{RP}\colon[/math] Для доказательства утверждения необходимо написать программу [math]p_{\mathrm{RP}}[/math], которая будет удолетворять ограничениям сложностного класса [math]\mathrm{RP}[/math]. [math]p_{\mathrm{RP}}(x)[/math] for [math]i = 1 \ldots k[/math] // [math]k[/math] будет определено позже if [math]p_{\mathrm{RP_{strong}}}(x)[/math] return [math]1[/math] return [math]0[/math] [math]k[/math] надо выбрать таким, чтобы выполнялось неравенство [math](\frac{1}{2^{q(|x|)}})^k \lt \frac{1}{2}[/math]. Отсюда [math]k \gt \frac{1}{q(|x|)}[/math].

[math]\triangleleft[/math]

Литература

• S.Arora, B.Barak. Randomized computation. Cambridge University, January 2007. [1]

См. также

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