Изменения

Перейти к: навигация, поиск

Классы RP и coRP

1657 байт добавлено, 23:19, 4 июня 2012
Нет описания правки
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>L</tex> таких, что существует программа [[Вероятностные вычисления. Вероятностная машина Тьюринга|ВМТ]] <tex>m</tex>такая, которая работает за полиномиальное время, ичто для любого <tex>x</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>;# <tex>T(m(x, r)) \le poly(|x|)</tex> для любой вероятностной ленты <tex>r</tex>.
}}
<tex>\mathrm{RP}</tex> — сложностный класс, допускающий ошибки программ на словах из <tex>L</tex>.
Заметим, что константа <tex>1/2</tex> в пункте 2 определения <tex>\mathrm{RP}</tex> может быть заменена на любую другую из промежутка <tex>(0, 1)</tex>, поскольку требуемой вероятности можно добиться множественным запуском программы.
 
<tex>\mathrm{RP}</tex> можно рассматривать как вероятностный аналог класса <tex>\mathrm{NP}</tex>, предполагая, что вероятность угадать сертификат в случае его существования не менее <tex>1/2</tex>.
 
{{Определение
|definition =
<tex>\mathrm{coRP} = \{L \bigm| \overline L \in \mathrm{RP}\}</tex>.
}}
Класс <tex>\mathrm{coRP}</tex> допускает ошибки программ на словах, не принадлежащих <tex>L</tex>.
 
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{weak}}</tex> состоит из языков <tex>L</tex> таких, что существует программа ВМТ <tex>m</tex>такая, которая работает за полиномиальное время, ичто для любого <tex>x</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(|x|)</tex> — некоторый полином, <tex>q(|x|) \geq 1</tex>;# <tex>T(m(x, r)) \le poly(|x|)</tex> для любой вероятностной ленты <tex>r</tex>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{strong}}</tex> состоит из языков <tex>L</tex> таких, что существует программа ВМТ <tex>m</tex>такая, которая работает за полиномиальное время, ичто для любого <tex>x</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(|x|)</tex> — некоторый полином;# <tex>T(m(x, r)) \le poly(|x|)</tex> для любой вероятностной ленты <tex>r</tex>.
}}
== Теорема об эквивалентности определений ==
{{Теорема
|statement=<tex>\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}</tex>.
|proof=
<tex>\mathrm{RP_{weak}} \subset \mathrm{RP}\colon</tex><br/>
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>m_p_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>m_p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>. <tex>m_p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>m_p_{\mathrm{RP_{weak}}}(x)</tex> '''then return''' <tex>1</tex>
'''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>m_p_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(m_p_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>m_p_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>m_p_{\mathrm{RP_{weak}}}</tex> равна меньше, чем <tex>1-\frac{1}{q(|x|)}</tex>, то есть вероятность ошибки программы <tex>m_p_{\mathrm{RP}}</tex> равна меньше, чем <tex>(1-\frac{1}{q(|x|)})^k</tex>. <tex>k</tex> надо выбрать таким, что вероятность ошибки программы <tex>m_{\mathrm{RP}}</tex> при <tex>x \in L</tex> была меньше <tex>\frac {1}{2}</tex>. Получается неравенство <tex>(1-\frac{1}{q(|x|)})^k < \frac{1}{2}</tex>. <br/> Логарифмируя, получаем: <br/> <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. <br/> Разложив логарифм в ряд Тейлора, получаем <br/> <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. <br/> Отсюда <tex>k > q(|x|)ln(2)</tex>.
<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex><br/>
Доказательство аналогично предыдущему пункту.
<tex>m_p_{\mathrm{RP_{weak}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>m_p_{\mathrm{RP}}(x)</tex> '''then return''' <tex>1</tex>
'''return''' <tex>0</tex>
Но здесь <tex>k</tex> выбирается так, чтобы выполнялось неравенство <br/> <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)}</tex>. Из него получается, что <br/>То есть <tex>k > log_2(q(|x|))</tex>.
<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex><br/>
Напишем программу <tex>m_p_{\mathrm{RP_{strong}}}</tex>, удолетворяющую ограничениям сложностного класса <tex>\mathrm{RP_{strong}}</tex>. <tex>m_p_{\mathrm{RP_{strong}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>m_p_{\mathrm{RP}}(x)</tex> '''then return''' <tex>1</tex>
'''return''' <tex>0</tex>
В этом случае <tex>k</tex> необходимо выбрать таким, что должно выполняться неравенство <tex>(\frac{1}{2})^k < 1 - \frac{1}{2^{q(|x|)}} \Leftrightarrow </tex>. То есть<br/><tex>k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. <br/>Разложив в ряд Тейлора получаем, что <br/> <tex>-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)} < \frac{1+q(|x|)}{ln(2)}</tex>. <br/>То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>.
<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex><br/>
Для доказательства утверждения необходимо написать программу <tex>m_p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>. <tex>m_p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>m_p_{\mathrm{RP_{strong}}}(x)</tex> '''then return''' <tex>1</tex>
'''return''' <tex>0</tex>
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство <br/><tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>. <br/> Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
}}
 
== Литература ==
* S.Arora, B.Barak. Randomized computation. Cambridge University, January 2007. [http://www.cs.princeton.edu/theory/complexity/bppchap.pdf]
== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
322
правки

Навигация