Викиконспекты - Вклад участника [ru]

Теория сложности

2012-06-04T20:50:46Z

Andrey.Eremeev: /* Вероятностные сложностные классы */

{{В разработке}}

[[Категория: Теория сложности]]

== Детерминированные и недетерминированные вычисления, сложность по времени и по памяти ==
*[[Сложностные классы. Вычисления с оракулом]]

=== Классы P и NP, NP-полнота ===
*[[Класс P]]
*[[Недетерминированные вычисления]]
*[[Классы NP и Σ₁]]
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
*[[Примеры NP-полных языков. Теорема Кука]]
*[[Теоремы о временной и емкостной иерархиях]]
*[[Теорема Бейкера — Гилла — Соловэя]]
*[[Теорема Ладнера]]
*[[Теорема Левина]]
*[[Теорема Бермана — Форчуна]]
*[[Теорема Махэни]]

=== Сложность по памяти, классы PS, L, NL, coNL ===
*[[Класс PS. Связь класса PS с другими классами теории сложности]]
*[[Теорема Сэвича. Совпадение классов NPS и PS]]
*[[PS-полнота языка верных булевых формул с кванторами (TQBF)]]
*[[Классы L, NL, coNL]]
*[[NL-полнота задачи о достижимости]]
*[[Теорема Иммермана]]

=== Полиномиальная иерархия ===
*[[Классы PH, Σ и Π]]
*[[Теоремы о коллапсе полиномиальной иерархии]]

== Схемная сложность ==
*[[Схемная сложность и класс P/poly]]
*[[Теорема Карпа — Липтона]]
*[[Классы NC и AC]]
*[[Теорема о непринадлежности XOR классу AC⁰]]

== Вероятностные сложностные классы ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
*[[Классы RP и coRP]]
*[[Класс ZPP]]
*[[Класс BPP и PP]]
*[[Соотношение вероятностных классов]]
*[[Теорема Лаутемана]]

=== Интерактивные протоколы ===
*[[Интерактивные протоколы. Класс IP. Класс AM]]
*[[Связь классов IP и AM друг с другом и с другими классами языков]]
*[[Арифметизация булевых формул с кванторами]]
*[[Лемма о соотношении coNP и IP]]
*[[Теорема Шамира]]
*[[Семейство универсальных попарно независимых хеш-функций]]
*[[Протокол Голдвассера-Сипсера для оценки размера множества]]

=== Probabilistically checkable proofs ===
*[[PCP-система]]
*[[PCP-теорема]]
*[[PCP-теорема, альтернативное доказательство | PCP-теорема, альтернативная формулировка]]

----

[[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется.

Классы BPP и PP

2012-06-04T20:50:24Z

Andrey.Eremeev: переименовал Класс BPP в Классы BPP и PP

==Определения==
{{Определение
|definition =
<tex>\mathrm{BPP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых существует такая [[Вероятностные вычисления. Вероятностная машина Тьюринга |ВМТ]] <tex>p</tex>, что для любого <tex>x</tex>:
# <tex>P(p(x) = [x \in L]) \ge 2/3</tex>;
# <tex>T(p, x) \le poly(|x|)</tex> для любой [[Вероятностные вычисления. Вероятностная машина Тьюринга |вероятностной ленты]].
}}

{{Определение
|definition =
<tex>\mathrm{PP}</tex> (от ''probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:
# <tex>\operatorname{P}(p(x) = [x \in L]) > 1/2</tex>;
# <tex>\forall r \operatorname{T}(p, x) \le poly(|x|)</tex>.
}}
<tex>\mathrm{PP}</tex> также допускает двусторонние ошибки, но является более широким по сравнению с <tex>\mathrm{BPP}</tex>.

<tex>\mathrm{BPP}</tex> — сложностный класс, допускающий двусторонние ошибки.
Константу <tex>2/3</tex> можно заменить на любое число из промежутка <tex>(1/2, 1)</tex>, так как требуемой вероятности можно добиться множественным запуском <tex>p</tex>. Замена константы на <tex>1/2</tex> сделала бы данный класс равным <tex>\Sigma^*</tex> (программа, возвращающая результат функции ''random''(), подошла бы для любого языка).

{{Определение
|definition=
<tex>\mathrm{BPP_{weak}}</tex> — класс языков <tex>L</tex>, для которых существует такая ВМТ <tex>p</tex>, что для любого <tex>x</tex>:
#<tex>P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(|x|)}</tex>, где <tex>q</tex>-полином и <tex>q(|x|) \ge 3</tex>;
#<tex>T(p, x) \le poly(|x|)</tex> для любой вероятностной ленты.
}}

{{Определение
|definition=
<tex>\mathrm{BPP_{strong}}</tex> — класс языков <tex>L</tex>, для которых существует такая ВМТ <tex>p</tex>, что для любого <tex>x</tex>:
#<tex>P(p(x)=[x \in L]) \ge 1 - \frac {1} {2^{q(|x|)}}</tex>, где <tex>q</tex>-полином и <tex>q(|x|) \ge 3</tex>;
#<tex>T(p, x) \le poly(|x|)</tex> для любой вероятностной ленты.
}}

==Теорема==
{{Теорема
|statement= <tex>\mathrm{BPP} = \mathrm{BPP_{weak}} = \mathrm{BPP_{strong}}</tex>.
|proof=
В доказательстве будет использоваться ''неравенство Чернова'': 
<tex>\forall p : \frac {1} {2} \le p \le 1: \sum\limits_{i = \lfloor \frac{n}{2} \rfloor + 1}^n \binom{n}{i}p^i (1 - p)^{n - i} \ge 1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2}</tex>

* Докажем, что <tex>\mathrm{BPP} = \mathrm{BPP_{weak}}</tex>
# <tex>\mathrm{BPP} \subseteq \mathrm{BPP_{weak}}</tex> Это следует из определений <tex>\mathrm{BPP}</tex> и <tex>\mathrm{BPP_{weak}}</tex>.
# <tex>\mathrm{BPP_{weak}} \subseteq \mathrm{BPP}</tex> Пусть <tex>L \in \mathrm{BPP_{weak}}</tex>. Тогда <tex>\exists p : P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(|x|)}</tex>. Построим ВМТ <tex>p_1</tex>, которая для входа <tex>x</tex> запускает <tex>p(x)</tex> <tex>n</tex> раз, и принимает <tex>x</tex>, если больше половины запусков принимают его. Подберем <tex>n</tex>, такое, что <tex>P(p_1(x)=[x \in L]) \ge \frac {2}{3}</tex> и <tex>T(p_1(x)) \le poly(|x|)</tex>. Вероятность <tex>P</tex> того, что <tex>p_1(x)</tex> даст правильный результат равна вероятности, что больше половины запусков <tex>p(x)</tex> дадут правильный результат. Тогда по схеме Бернулли <tex>P = \sum\limits_{i = \lfloor \frac{n}{2} \rfloor + 1}^n \binom{n}{i}p^i (1 - p)^{n - i}</tex>, где <tex>p=\frac {1}{2} + \frac {1} {q(|x|)}</tex> — вероятность, что запуск <tex>p(x)</tex> даст правильный ответ. По неравенству Чернова : <tex> P \ge 1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} </tex>. То есть для того, чтобы <tex>P(p(x)=[x \in L]) \ge \frac {2}{3}</tex> достаточно подобрать такое <tex>n</tex>, что <tex>1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} \ge \frac {2}{3}</tex>. Получаем, что <tex>n \ge \frac {\ln 3} {2(p - \frac {1} {2})^2} = \frac {{q(|x|)}^2 \ln 3}{2} </tex>. Возьмем <tex>n = \lceil \frac {{q(|x|)}^2 \ln 3}{2} \rceil </tex>, тогда неравенство <tex>T(p_1(x)) \le poly(|x|)</tex> будет выполнено.

* Докажем, что <tex>\mathrm{BPP} = \mathrm{BPP_{strong}}</tex>
# <tex>\mathrm{BPP_{strong}} \subseteq \mathrm{BPP} </tex> Это следует из определений <tex>\mathrm{BPP}</tex> и <tex>\mathrm{BPP_{strong}}</tex>.
# <tex>\mathrm{BPP} \subseteq \mathrm{BPP_{strong}}</tex> Пусть <tex>L \in \mathrm{BPP}</tex>. Тогда <tex>\exists p : P(p(x)=[x \in L]) \ge \frac {2}{3}</tex>. Построим ВМТ <tex>p_1</tex>, которая для входа <tex>x</tex> запускает <tex>p(x)</tex> <tex>n</tex> раз, и принимает <tex>x</tex>, если больше половины запусков принимают его. Подберем <tex>n</tex>, такое, что <tex>P(p_1(x)=[x \in L]) \ge 1 - \frac {1}{2^{q(|x|)}}</tex> и <tex>T(p_1(x)) \le poly(|x|)</tex>. Проводя рассуждения, аналогичные изложенным в доказательстве <tex>\mathrm{BPP_{weak}} \subseteq \mathrm{BPP}</tex>, получаем, что <tex>1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} \ge 1 - \frac {1}{2^{q(|x|)}}</tex>, где <tex>p = \frac {2} {3}</tex>. Отсюда <tex>n \ge \frac {{q(|x|)} \ln 2}{2({\frac {2}{3} - \frac {1}{2}})^2} </tex>. Возьмем <tex>n = \lceil 18 {q(|x|)} \ln 2 \rceil </tex>, тогда неравенство <tex>T(p_1(x)) \le poly(|x|)</tex> будет выполнено.
}}

== См. также ==
* [[Вероятностные вычисления. Вероятностная машина Тьюринга]] 
* [http://en.wikipedia.org/wiki/Chernoff_bound Неравенство Чернова]

[[Категория: Теория сложности]]

Класс BPP

2012-06-04T20:50:24Z

Andrey.Eremeev: переименовал Класс BPP в Классы BPP и PP

#перенаправление [[Классы BPP и PP]]

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

2012-06-04T20:32:23Z

Andrey.Eremeev: /* Вероятностные классы сложности */

[[Категория: Теория сложности]]
'''Вероятностные вычисления''' — один из подходов в теории вычислительной сложности, в котором программы получают доступ, говоря неформально, к генератору случайных чисел. Мы рассмотрим классы сложности, для которых программы могут работать за полиномиальное время и делать односторонние, двусторонние ошибки или работать за полиномиальное время лишь в среднем случае.

== Основные определения ==
{{Определение
|definition =
'''Вероятностная лента''' — бесконечная в одну сторону последовательность битов, распределение которых подчиняется некоторому вероятностному закону (обычно считают, что биты в различных позициях независимы и вероятность нахождения <tex>0</tex> или <tex>1</tex> в каждой позиции равна <tex>1/2</tex>).
}}
{{Определение
|definition =
'''Вероятностная машина Тьюринга''' (ВМТ) — детерминированная машина Тьюринга, имеющая вероятностную ленту. Переходы в ВМТ могут осуществляться с учетом информации, считанной с вероятностной ленты.
}}

Используя тезис Черча-Тьюринга, ВМТ можно сопоставить программы, имеющие доступ к случайным битам. Обращение к очередному биту можно трактовать как вызов специальной функции ''random''(). При этом также будем предполагать, что вероятностная лента является неявным аргументом программы или ВМТ, т.е. <tex>p(x) = p(x, r)</tex>, где <tex>r</tex> — вероятностная лента.

Введем [http://ru.wikipedia.org/wiki/Вероятностное_пространство вероятностное пространство] <tex>(\Omega, \Sigma, \operatorname{P})</tex>, где пространство элементарных исходов <tex>\Omega</tex> — множество всех вероятностных лент, <tex>\Sigma</tex> — сигма-алгебра подмножеств <tex>\Omega</tex>, <tex>\operatorname{P}</tex> — вероятностная мера, заданная на <tex>\Sigma</tex>. Будем считать, что <tex>\Sigma</tex> порождена событиями, зависящими лишь от конечного числа бит вероятностной ленты (то есть существующими в дискретных вероятностных пространствах). Покажем, что любой предикат от ВМТ является событием.
{{Теорема
|statement= Пусть <tex>m</tex> — ВМТ. Тогда для любых <tex>x</tex> и <tex>A</tex> — предиката от <tex>m</tex> выполняется <tex>R = \{r \bigm| A(m(x, r))\} \in \Sigma</tex>, т.е. <tex>R</tex> измеримо.
|proof=
<tex>R = \bigcup\limits_{i = 0}^\infty R_i</tex>, где <tex>R_i = \{r \bigm| A(m(x, r)), m</tex> прочитала ровно <tex>i</tex> первых символов с <tex>r\}</tex>. Это верно, поскольку мы рассматриваем только завершающиеся ВМТ. Кроме того, из определения <tex>R_i</tex> следует, что они дизъюнктны.

<tex>R_i \in \Sigma</tex> как зависящие от <tex>i</tex> первых битов вероятностной ленты, <tex>\operatorname{P}(R_i) = \frac{1}{2^i} \cdot |\{s \bigm| |s| = i, s</tex> — префикс <tex>r \in R_i\}|</tex>.

<tex>R \in \Sigma</tex> как счетное объединение событий, при этом из их дизъюнктности следует, что <tex>\operatorname{P}(R) = \sum\limits_{i = 0}^{\infty} \operatorname{P}(R_i)</tex>.
}}

== Соотношение вероятностных классов ==
{{Теорема
|statement = <tex>\mathrm{RP} \subset \mathrm{NP} \subset \mathrm{PP} \subset \mathrm{PS}</tex>.
|proof =
1. <tex>\mathrm{RP} \subset \mathrm{NP}</tex>. Если в программе для <tex>L \in \mathrm{RP}</tex> заменить все вызовы ''random''() на недетерминированный выбор, то получим программу для <tex>L</tex> с ограничениями <tex>\mathrm{NP}</tex>.

2. <tex>\mathrm{NP} \subset \mathrm{PP}</tex>. Приведем программу <tex>q</tex> с ограничениями класса <tex>\mathrm{PP}</tex>, которая разрешает <tex>L \in \mathrm{NP}</tex>. Пусть функция ''infair_coin''() моделирует нечестную монету, а именно возвращает единицу с вероятностью <tex>1/2 - \varepsilon</tex>, где <tex>\varepsilon</tex> мы определим позже, и ноль с вероятностью <tex>1/2 + \varepsilon</tex>. Пусть также <tex>V</tex> — верификатор сертификатов для <tex>L</tex>. Тогда <tex>q</tex> будет выглядеть следующим образом:
<tex>q</tex>(x)
c <- случайный сертификат
'''if''' <tex>V</tex>(x, c)
'''return''' 1
'''return''' infair_coin()
Необходимо удовлетворить условию <tex>\operatorname{P}(q(x) = [x \in L]) > 1/2</tex>.

Пусть <tex>x \notin L</tex>. В этом случае <tex>V(x, c)</tex> вернет <tex>0</tex> и результат работы программы будет зависеть от нечестной монеты. Она вернет <tex>0</tex> с вероятностью <tex>1/2 + \varepsilon > 1/2</tex>.

Пусть <tex>x \in L</tex>. Тогда [[Формула полной вероятности|по формуле полной вероятности]] <tex>\operatorname{P}(q(x) = 1) = p_0 + (1 - p_0) (1/2 - \varepsilon)</tex>, где <tex>p_0</tex> — вероятность угадать правильный сертификат. Заметим, что поскольку длина всех сертификатов ограничена некоторым полиномом <tex>s(n), n = |x|</tex> и существует хотя бы один правильный сертификат, <tex>p_0 \ge 2^{-s(n)}</tex>. Найдем <tex>\varepsilon</tex> из неравенства <tex>\operatorname{P}(q(x) = 1) > 1/2</tex>:

<tex>p_0 + 1/2 - \varepsilon - p_0 / 2 + p_0 \varepsilon > 1/2</tex>;

<tex>p_0 / 2 + (p_0 - 1)\varepsilon > 0</tex>;

<tex>\varepsilon < \frac{p_0}{2 (1 - p_0)}</tex>.

Достаточно взять <tex>\varepsilon \le p_0 / 2</tex>. Из сделанного выше замечания следует, что работу функции ''infair_coin''() можно смоделировать с помощью не более чем <tex>s(n) + 1</tex> вызовов ''random''(). Также учтем, что длина сертификата и время работы <tex>V</tex> полиномиальны относительно <tex>|x|</tex>. Таким образом, мы построили программу <tex>q</tex>, удовлетворяющую ограничениям класса <tex>\mathrm{PP}</tex>.

3. <tex>\mathrm{PP} \subset \mathrm{PS}</tex>. Пусть <tex>p</tex> — программа для языка <tex>L \in \mathrm{PP}</tex>. Она используют не более чем полиномиальное количество вероятностных бит, так как сама работает за полиномиальное время. Тогда программа для <tex>\mathrm{PS}</tex> будет перебирать все участки вероятностных лент нужной полиномиальной длины и запускать на них <tex>p</tex>. Ответом будет <tex>0</tex> или <tex>1</tex> в зависимости от того, каких ответов <tex>p</tex> оказалось больше.
}}

== См. также ==
* [[Класс BPP]]
* [[Классы RP и coRP]]
* [[Теорема Лаутемана]]

== Литература ==
* [http://www.cs.princeton.edu/theory/complexity/ Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach]

Классы BPP и PP

2012-06-04T20:32:12Z

Andrey.Eremeev: /* Определения */

==Определения==
{{Определение
|definition =
<tex>\mathrm{BPP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых существует такая [[Вероятностные вычисления. Вероятностная машина Тьюринга |ВМТ]] <tex>p</tex>, что для любого <tex>x</tex>:
# <tex>P(p(x) = [x \in L]) \ge 2/3</tex>;
# <tex>T(p, x) \le poly(|x|)</tex> для любой [[Вероятностные вычисления. Вероятностная машина Тьюринга |вероятностной ленты]].
}}

{{Определение
|definition =
<tex>\mathrm{PP}</tex> (от ''probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:
# <tex>\operatorname{P}(p(x) = [x \in L]) > 1/2</tex>;
# <tex>\forall r \operatorname{T}(p, x) \le poly(|x|)</tex>.
}}
<tex>\mathrm{PP}</tex> также допускает двусторонние ошибки, но является более широким по сравнению с <tex>\mathrm{BPP}</tex>.

<tex>\mathrm{BPP}</tex> — сложностный класс, допускающий двусторонние ошибки.
Константу <tex>2/3</tex> можно заменить на любое число из промежутка <tex>(1/2, 1)</tex>, так как требуемой вероятности можно добиться множественным запуском <tex>p</tex>. Замена константы на <tex>1/2</tex> сделала бы данный класс равным <tex>\Sigma^*</tex> (программа, возвращающая результат функции ''random''(), подошла бы для любого языка).

{{Определение
|definition=
<tex>\mathrm{BPP_{weak}}</tex> — класс языков <tex>L</tex>, для которых существует такая ВМТ <tex>p</tex>, что для любого <tex>x</tex>:
#<tex>P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(|x|)}</tex>, где <tex>q</tex>-полином и <tex>q(|x|) \ge 3</tex>;
#<tex>T(p, x) \le poly(|x|)</tex> для любой вероятностной ленты.
}}

{{Определение
|definition=
<tex>\mathrm{BPP_{strong}}</tex> — класс языков <tex>L</tex>, для которых существует такая ВМТ <tex>p</tex>, что для любого <tex>x</tex>:
#<tex>P(p(x)=[x \in L]) \ge 1 - \frac {1} {2^{q(|x|)}}</tex>, где <tex>q</tex>-полином и <tex>q(|x|) \ge 3</tex>;
#<tex>T(p, x) \le poly(|x|)</tex> для любой вероятностной ленты.
}}

==Теорема==
{{Теорема
|statement= <tex>\mathrm{BPP} = \mathrm{BPP_{weak}} = \mathrm{BPP_{strong}}</tex>.
|proof=
В доказательстве будет использоваться ''неравенство Чернова'': 
<tex>\forall p : \frac {1} {2} \le p \le 1: \sum\limits_{i = \lfloor \frac{n}{2} \rfloor + 1}^n \binom{n}{i}p^i (1 - p)^{n - i} \ge 1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2}</tex>

* Докажем, что <tex>\mathrm{BPP} = \mathrm{BPP_{weak}}</tex>
# <tex>\mathrm{BPP} \subseteq \mathrm{BPP_{weak}}</tex> Это следует из определений <tex>\mathrm{BPP}</tex> и <tex>\mathrm{BPP_{weak}}</tex>.
# <tex>\mathrm{BPP_{weak}} \subseteq \mathrm{BPP}</tex> Пусть <tex>L \in \mathrm{BPP_{weak}}</tex>. Тогда <tex>\exists p : P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(|x|)}</tex>. Построим ВМТ <tex>p_1</tex>, которая для входа <tex>x</tex> запускает <tex>p(x)</tex> <tex>n</tex> раз, и принимает <tex>x</tex>, если больше половины запусков принимают его. Подберем <tex>n</tex>, такое, что <tex>P(p_1(x)=[x \in L]) \ge \frac {2}{3}</tex> и <tex>T(p_1(x)) \le poly(|x|)</tex>. Вероятность <tex>P</tex> того, что <tex>p_1(x)</tex> даст правильный результат равна вероятности, что больше половины запусков <tex>p(x)</tex> дадут правильный результат. Тогда по схеме Бернулли <tex>P = \sum\limits_{i = \lfloor \frac{n}{2} \rfloor + 1}^n \binom{n}{i}p^i (1 - p)^{n - i}</tex>, где <tex>p=\frac {1}{2} + \frac {1} {q(|x|)}</tex> — вероятность, что запуск <tex>p(x)</tex> даст правильный ответ. По неравенству Чернова : <tex> P \ge 1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} </tex>. То есть для того, чтобы <tex>P(p(x)=[x \in L]) \ge \frac {2}{3}</tex> достаточно подобрать такое <tex>n</tex>, что <tex>1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} \ge \frac {2}{3}</tex>. Получаем, что <tex>n \ge \frac {\ln 3} {2(p - \frac {1} {2})^2} = \frac {{q(|x|)}^2 \ln 3}{2} </tex>. Возьмем <tex>n = \lceil \frac {{q(|x|)}^2 \ln 3}{2} \rceil </tex>, тогда неравенство <tex>T(p_1(x)) \le poly(|x|)</tex> будет выполнено.

* Докажем, что <tex>\mathrm{BPP} = \mathrm{BPP_{strong}}</tex>
# <tex>\mathrm{BPP_{strong}} \subseteq \mathrm{BPP} </tex> Это следует из определений <tex>\mathrm{BPP}</tex> и <tex>\mathrm{BPP_{strong}}</tex>.
# <tex>\mathrm{BPP} \subseteq \mathrm{BPP_{strong}}</tex> Пусть <tex>L \in \mathrm{BPP}</tex>. Тогда <tex>\exists p : P(p(x)=[x \in L]) \ge \frac {2}{3}</tex>. Построим ВМТ <tex>p_1</tex>, которая для входа <tex>x</tex> запускает <tex>p(x)</tex> <tex>n</tex> раз, и принимает <tex>x</tex>, если больше половины запусков принимают его. Подберем <tex>n</tex>, такое, что <tex>P(p_1(x)=[x \in L]) \ge 1 - \frac {1}{2^{q(|x|)}}</tex> и <tex>T(p_1(x)) \le poly(|x|)</tex>. Проводя рассуждения, аналогичные изложенным в доказательстве <tex>\mathrm{BPP_{weak}} \subseteq \mathrm{BPP}</tex>, получаем, что <tex>1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} \ge 1 - \frac {1}{2^{q(|x|)}}</tex>, где <tex>p = \frac {2} {3}</tex>. Отсюда <tex>n \ge \frac {{q(|x|)} \ln 2}{2({\frac {2}{3} - \frac {1}{2}})^2} </tex>. Возьмем <tex>n = \lceil 18 {q(|x|)} \ln 2 \rceil </tex>, тогда неравенство <tex>T(p_1(x)) \le poly(|x|)</tex> будет выполнено.
}}

{{Теорема
|statement =
<tex>\mathrm{RP} \cup \mathrm{coRP} \subset \mathrm{BPP}</tex>.
|proof =
Пусть <tex>p</tex> — программа для <tex>L \in \mathrm{RP}</tex>. Программу <tex>q</tex> для <tex>\mathrm{BPP}</tex> определим следующим образом:
<tex>q</tex>(x)
u <- <tex>p</tex>(x)
v <- <tex>p</tex>(x)
'''return''' u '''or''' v
Пусть <tex>x \in L</tex>. В этом случае вероятность ошибки равна <tex>\operatorname{P}(u = 0, v = 0) = \operatorname{P}(u = 0) \cdot \operatorname{P}(v = 0) \le 1/4</tex>.

Пусть <tex>x \notin L</tex>. Тогда с вероятностью <tex>1</tex> будет верно <tex>u = 0, v = 0</tex> и <tex>q</tex> вернет правильный ответ.

Аналогично доказывается, что <tex>\mathrm{coRP} \subset \mathrm{BPP}</tex>.
}}

== См. также ==
* [[Вероятностные вычисления. Вероятностная машина Тьюринга]] 
* [http://en.wikipedia.org/wiki/Chernoff_bound Неравенство Чернова]

[[Категория: Теория сложности]]

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

2012-06-04T20:17:10Z

Andrey.Eremeev: /* См. также */

[[Категория: Теория сложности]]
'''Вероятностные вычисления''' — один из подходов в теории вычислительной сложности, в котором программы получают доступ, говоря неформально, к генератору случайных чисел. Мы рассмотрим классы сложности, для которых программы могут работать за полиномиальное время и делать односторонние, двусторонние ошибки или работать за полиномиальное время лишь в среднем случае.

== Основные определения ==
{{Определение
|definition =
'''Вероятностная лента''' — бесконечная в одну сторону последовательность битов, распределение которых подчиняется некоторому вероятностному закону (обычно считают, что биты в различных позициях независимы и вероятность нахождения <tex>0</tex> или <tex>1</tex> в каждой позиции равна <tex>1/2</tex>).
}}
{{Определение
|definition =
'''Вероятностная машина Тьюринга''' (ВМТ) — детерминированная машина Тьюринга, имеющая вероятностную ленту. Переходы в ВМТ могут осуществляться с учетом информации, считанной с вероятностной ленты.
}}

Используя тезис Черча-Тьюринга, ВМТ можно сопоставить программы, имеющие доступ к случайным битам. Обращение к очередному биту можно трактовать как вызов специальной функции ''random''(). При этом также будем предполагать, что вероятностная лента является неявным аргументом программы или ВМТ, т.е. <tex>p(x) = p(x, r)</tex>, где <tex>r</tex> — вероятностная лента.

Введем [http://ru.wikipedia.org/wiki/Вероятностное_пространство вероятностное пространство] <tex>(\Omega, \Sigma, \operatorname{P})</tex>, где пространство элементарных исходов <tex>\Omega</tex> — множество всех вероятностных лент, <tex>\Sigma</tex> — сигма-алгебра подмножеств <tex>\Omega</tex>, <tex>\operatorname{P}</tex> — вероятностная мера, заданная на <tex>\Sigma</tex>. Будем считать, что <tex>\Sigma</tex> порождена событиями, зависящими лишь от конечного числа бит вероятностной ленты (то есть существующими в дискретных вероятностных пространствах). Покажем, что любой предикат от ВМТ является событием.
{{Теорема
|statement= Пусть <tex>m</tex> — ВМТ. Тогда для любых <tex>x</tex> и <tex>A</tex> — предиката от <tex>m</tex> выполняется <tex>R = \{r \bigm| A(m(x, r))\} \in \Sigma</tex>, т.е. <tex>R</tex> измеримо.
|proof=
<tex>R = \bigcup\limits_{i = 0}^\infty R_i</tex>, где <tex>R_i = \{r \bigm| A(m(x, r)), m</tex> прочитала ровно <tex>i</tex> первых символов с <tex>r\}</tex>. Это верно, поскольку мы рассматриваем только завершающиеся ВМТ. Кроме того, из определения <tex>R_i</tex> следует, что они дизъюнктны.

<tex>R_i \in \Sigma</tex> как зависящие от <tex>i</tex> первых битов вероятностной ленты, <tex>\operatorname{P}(R_i) = \frac{1}{2^i} \cdot |\{s \bigm| |s| = i, s</tex> — префикс <tex>r \in R_i\}|</tex>.

<tex>R \in \Sigma</tex> как счетное объединение событий, при этом из их дизъюнктности следует, что <tex>\operatorname{P}(R) = \sum\limits_{i = 0}^{\infty} \operatorname{P}(R_i)</tex>.
}}

== Вероятностные классы сложности ==
{{Определение
|definition =
<tex>\mathrm{RP}</tex> (от ''randomized polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:
# <tex>x \notin L \Rightarrow \operatorname{P}(p(x) = 0) = 1</tex>; 
# <tex>x \in L \Rightarrow \operatorname{P}(p(x) = 1) \ge 1/2</tex>; 
# <tex>\forall r \operatorname{T}(p, x) \le poly(|x|).</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{PP}</tex> (от ''probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:
# <tex>\operatorname{P}(p(x) = [x \in L]) > 1/2</tex>;
# <tex>\forall r \operatorname{T}(p, x) \le poly(|x|)</tex>.
}}
<tex>\mathrm{PP}</tex> также допускает двусторонние ошибки, но является более широким по сравнению с <tex>\mathrm{BPP}</tex>.

== Соотношение вероятностных классов ==
{{Теорема
|statement = <tex>\mathrm{RP} \subset \mathrm{NP} \subset \mathrm{PP} \subset \mathrm{PS}</tex>.
|proof =
1. <tex>\mathrm{RP} \subset \mathrm{NP}</tex>. Если в программе для <tex>L \in \mathrm{RP}</tex> заменить все вызовы ''random''() на недетерминированный выбор, то получим программу для <tex>L</tex> с ограничениями <tex>\mathrm{NP}</tex>.

2. <tex>\mathrm{NP} \subset \mathrm{PP}</tex>. Приведем программу <tex>q</tex> с ограничениями класса <tex>\mathrm{PP}</tex>, которая разрешает <tex>L \in \mathrm{NP}</tex>. Пусть функция ''infair_coin''() моделирует нечестную монету, а именно возвращает единицу с вероятностью <tex>1/2 - \varepsilon</tex>, где <tex>\varepsilon</tex> мы определим позже, и ноль с вероятностью <tex>1/2 + \varepsilon</tex>. Пусть также <tex>V</tex> — верификатор сертификатов для <tex>L</tex>. Тогда <tex>q</tex> будет выглядеть следующим образом:
<tex>q</tex>(x)
c <- случайный сертификат
'''if''' <tex>V</tex>(x, c)
'''return''' 1
'''return''' infair_coin()
Необходимо удовлетворить условию <tex>\operatorname{P}(q(x) = [x \in L]) > 1/2</tex>.

Пусть <tex>x \notin L</tex>. В этом случае <tex>V(x, c)</tex> вернет <tex>0</tex> и результат работы программы будет зависеть от нечестной монеты. Она вернет <tex>0</tex> с вероятностью <tex>1/2 + \varepsilon > 1/2</tex>.

Пусть <tex>x \in L</tex>. Тогда [[Формула полной вероятности|по формуле полной вероятности]] <tex>\operatorname{P}(q(x) = 1) = p_0 + (1 - p_0) (1/2 - \varepsilon)</tex>, где <tex>p_0</tex> — вероятность угадать правильный сертификат. Заметим, что поскольку длина всех сертификатов ограничена некоторым полиномом <tex>s(n), n = |x|</tex> и существует хотя бы один правильный сертификат, <tex>p_0 \ge 2^{-s(n)}</tex>. Найдем <tex>\varepsilon</tex> из неравенства <tex>\operatorname{P}(q(x) = 1) > 1/2</tex>:

<tex>p_0 + 1/2 - \varepsilon - p_0 / 2 + p_0 \varepsilon > 1/2</tex>;

<tex>p_0 / 2 + (p_0 - 1)\varepsilon > 0</tex>;

<tex>\varepsilon < \frac{p_0}{2 (1 - p_0)}</tex>.

Достаточно взять <tex>\varepsilon \le p_0 / 2</tex>. Из сделанного выше замечания следует, что работу функции ''infair_coin''() можно смоделировать с помощью не более чем <tex>s(n) + 1</tex> вызовов ''random''(). Также учтем, что длина сертификата и время работы <tex>V</tex> полиномиальны относительно <tex>|x|</tex>. Таким образом, мы построили программу <tex>q</tex>, удовлетворяющую ограничениям класса <tex>\mathrm{PP}</tex>.

3. <tex>\mathrm{PP} \subset \mathrm{PS}</tex>. Пусть <tex>p</tex> — программа для языка <tex>L \in \mathrm{PP}</tex>. Она используют не более чем полиномиальное количество вероятностных бит, так как сама работает за полиномиальное время. Тогда программа для <tex>\mathrm{PS}</tex> будет перебирать все участки вероятностных лент нужной полиномиальной длины и запускать на них <tex>p</tex>. Ответом будет <tex>0</tex> или <tex>1</tex> в зависимости от того, каких ответов <tex>p</tex> оказалось больше.
}}

== См. также ==
* [[Класс BPP]]
* [[Классы RP и coRP]]
* [[Теорема Лаутемана]]

== Литература ==
* [http://www.cs.princeton.edu/theory/complexity/ Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach]

Классы BPP и PP

2012-06-04T20:14:02Z

Andrey.Eremeev:

==Определения==
{{Определение
|definition =
<tex>\mathrm{BPP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых существует такая [[Вероятностные вычисления. Вероятностная машина Тьюринга |ВМТ]] <tex>p</tex>, что для любого <tex>x</tex>:
# <tex>P(p(x) = [x \in L]) \ge 2/3</tex>;
# <tex>T(p, x) \le poly(|x|)</tex> для любой [[Вероятностные вычисления. Вероятностная машина Тьюринга |вероятностной ленты]].
}}

<tex>\mathrm{BPP}</tex> — сложностный класс, допускающий двусторонние ошибки.
Константу <tex>2/3</tex> можно заменить на любое число из промежутка <tex>(1/2, 1)</tex>, так как требуемой вероятности можно добиться множественным запуском <tex>p</tex>. Замена константы на <tex>1/2</tex> сделала бы данный класс равным <tex>\Sigma^*</tex> (программа, возвращающая результат функции ''random''(), подошла бы для любого языка).

{{Определение
|definition=
<tex>\mathrm{BPP_{weak}}</tex> — класс языков <tex>L</tex>, для которых существует такая ВМТ <tex>p</tex>, что для любого <tex>x</tex>:
#<tex>P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(|x|)}</tex>, где <tex>q</tex>-полином и <tex>q(|x|) \ge 3</tex>;
#<tex>T(p, x) \le poly(|x|)</tex> для любой вероятностной ленты.
}}

{{Определение
|definition=
<tex>\mathrm{BPP_{strong}}</tex> — класс языков <tex>L</tex>, для которых существует такая ВМТ <tex>p</tex>, что для любого <tex>x</tex>:
#<tex>P(p(x)=[x \in L]) \ge 1 - \frac {1} {2^{q(|x|)}}</tex>, где <tex>q</tex>-полином и <tex>q(|x|) \ge 3</tex>;
#<tex>T(p, x) \le poly(|x|)</tex> для любой вероятностной ленты.
}}

==Теорема==
{{Теорема
|statement= <tex>\mathrm{BPP} = \mathrm{BPP_{weak}} = \mathrm{BPP_{strong}}</tex>.
|proof=
В доказательстве будет использоваться ''неравенство Чернова'': 
<tex>\forall p : \frac {1} {2} \le p \le 1: \sum\limits_{i = \lfloor \frac{n}{2} \rfloor + 1}^n \binom{n}{i}p^i (1 - p)^{n - i} \ge 1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2}</tex>

* Докажем, что <tex>\mathrm{BPP} = \mathrm{BPP_{weak}}</tex>
# <tex>\mathrm{BPP} \subseteq \mathrm{BPP_{weak}}</tex> Это следует из определений <tex>\mathrm{BPP}</tex> и <tex>\mathrm{BPP_{weak}}</tex>.
# <tex>\mathrm{BPP_{weak}} \subseteq \mathrm{BPP}</tex> Пусть <tex>L \in \mathrm{BPP_{weak}}</tex>. Тогда <tex>\exists p : P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(|x|)}</tex>. Построим ВМТ <tex>p_1</tex>, которая для входа <tex>x</tex> запускает <tex>p(x)</tex> <tex>n</tex> раз, и принимает <tex>x</tex>, если больше половины запусков принимают его. Подберем <tex>n</tex>, такое, что <tex>P(p_1(x)=[x \in L]) \ge \frac {2}{3}</tex> и <tex>T(p_1(x)) \le poly(|x|)</tex>. Вероятность <tex>P</tex> того, что <tex>p_1(x)</tex> даст правильный результат равна вероятности, что больше половины запусков <tex>p(x)</tex> дадут правильный результат. Тогда по схеме Бернулли <tex>P = \sum\limits_{i = \lfloor \frac{n}{2} \rfloor + 1}^n \binom{n}{i}p^i (1 - p)^{n - i}</tex>, где <tex>p=\frac {1}{2} + \frac {1} {q(|x|)}</tex> — вероятность, что запуск <tex>p(x)</tex> даст правильный ответ. По неравенству Чернова : <tex> P \ge 1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} </tex>. То есть для того, чтобы <tex>P(p(x)=[x \in L]) \ge \frac {2}{3}</tex> достаточно подобрать такое <tex>n</tex>, что <tex>1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} \ge \frac {2}{3}</tex>. Получаем, что <tex>n \ge \frac {\ln 3} {2(p - \frac {1} {2})^2} = \frac {{q(|x|)}^2 \ln 3}{2} </tex>. Возьмем <tex>n = \lceil \frac {{q(|x|)}^2 \ln 3}{2} \rceil </tex>, тогда неравенство <tex>T(p_1(x)) \le poly(|x|)</tex> будет выполнено.

* Докажем, что <tex>\mathrm{BPP} = \mathrm{BPP_{strong}}</tex>
# <tex>\mathrm{BPP_{strong}} \subseteq \mathrm{BPP} </tex> Это следует из определений <tex>\mathrm{BPP}</tex> и <tex>\mathrm{BPP_{strong}}</tex>.
# <tex>\mathrm{BPP} \subseteq \mathrm{BPP_{strong}}</tex> Пусть <tex>L \in \mathrm{BPP}</tex>. Тогда <tex>\exists p : P(p(x)=[x \in L]) \ge \frac {2}{3}</tex>. Построим ВМТ <tex>p_1</tex>, которая для входа <tex>x</tex> запускает <tex>p(x)</tex> <tex>n</tex> раз, и принимает <tex>x</tex>, если больше половины запусков принимают его. Подберем <tex>n</tex>, такое, что <tex>P(p_1(x)=[x \in L]) \ge 1 - \frac {1}{2^{q(|x|)}}</tex> и <tex>T(p_1(x)) \le poly(|x|)</tex>. Проводя рассуждения, аналогичные изложенным в доказательстве <tex>\mathrm{BPP_{weak}} \subseteq \mathrm{BPP}</tex>, получаем, что <tex>1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} \ge 1 - \frac {1}{2^{q(|x|)}}</tex>, где <tex>p = \frac {2} {3}</tex>. Отсюда <tex>n \ge \frac {{q(|x|)} \ln 2}{2({\frac {2}{3} - \frac {1}{2}})^2} </tex>. Возьмем <tex>n = \lceil 18 {q(|x|)} \ln 2 \rceil </tex>, тогда неравенство <tex>T(p_1(x)) \le poly(|x|)</tex> будет выполнено.
}}

{{Теорема
|statement =
<tex>\mathrm{RP} \cup \mathrm{coRP} \subset \mathrm{BPP}</tex>.
|proof =
Пусть <tex>p</tex> — программа для <tex>L \in \mathrm{RP}</tex>. Программу <tex>q</tex> для <tex>\mathrm{BPP}</tex> определим следующим образом:
<tex>q</tex>(x)
u <- <tex>p</tex>(x)
v <- <tex>p</tex>(x)
'''return''' u '''or''' v
Пусть <tex>x \in L</tex>. В этом случае вероятность ошибки равна <tex>\operatorname{P}(u = 0, v = 0) = \operatorname{P}(u = 0) \cdot \operatorname{P}(v = 0) \le 1/4</tex>.

Пусть <tex>x \notin L</tex>. Тогда с вероятностью <tex>1</tex> будет верно <tex>u = 0, v = 0</tex> и <tex>q</tex> вернет правильный ответ.

Аналогично доказывается, что <tex>\mathrm{coRP} \subset \mathrm{BPP}</tex>.
}}

== См. также ==
* [[Вероятностные вычисления. Вероятностная машина Тьюринга]] 
* [http://en.wikipedia.org/wiki/Chernoff_bound Неравенство Чернова]

[[Категория: Теория сложности]]

Теория сложности

2012-06-04T20:13:38Z

Andrey.Eremeev: /* Вероятностные сложностные классы */

{{В разработке}}

[[Категория: Теория сложности]]

== Детерминированные и недетерминированные вычисления, сложность по времени и по памяти ==
*[[Сложностные классы. Вычисления с оракулом]]

=== Классы P и NP, NP-полнота ===
*[[Класс P]]
*[[Недетерминированные вычисления]]
*[[Классы NP и Σ₁]]
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
*[[Примеры NP-полных языков. Теорема Кука]]
*[[Теоремы о временной и емкостной иерархиях]]
*[[Теорема Бейкера — Гилла — Соловэя]]
*[[Теорема Ладнера]]
*[[Теорема Левина]]
*[[Теорема Бермана — Форчуна]]
*[[Теорема Махэни]]

=== Сложность по памяти, классы PS, L, NL, coNL ===
*[[Класс PS. Связь класса PS с другими классами теории сложности]]
*[[Теорема Сэвича. Совпадение классов NPS и PS]]
*[[PS-полнота языка верных булевых формул с кванторами (TQBF)]]
*[[Классы L, NL, coNL]]
*[[NL-полнота задачи о достижимости]]
*[[Теорема Иммермана]]

=== Полиномиальная иерархия ===
*[[Классы PH, Σ и Π]]
*[[Теоремы о коллапсе полиномиальной иерархии]]

== Схемная сложность ==
*[[Схемная сложность и класс P/poly]]
*[[Теорема Карпа — Липтона]]
*[[Классы NC и AC]]
*[[Теорема о непринадлежности XOR классу AC⁰]]

== Вероятностные сложностные классы ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
*[[Классы RP и coRP]]
*[[Класс ZPP]]
*[[Класс BPP]]
*[[Теорема Лаутемана]]

=== Интерактивные протоколы ===
*[[Интерактивные протоколы. Класс IP. Класс AM]]
*[[Связь классов IP и AM друг с другом и с другими классами языков]]
*[[Арифметизация булевых формул с кванторами]]
*[[Лемма о соотношении coNP и IP]]
*[[Теорема Шамира]]
*[[Семейство универсальных попарно независимых хеш-функций]]
*[[Протокол Голдвассера-Сипсера для оценки размера множества]]

=== Probabilistically checkable proofs ===
*[[PCP-система]]
*[[PCP-теорема]]
*[[PCP-теорема, альтернативное доказательство | PCP-теорема, альтернативная формулировка]]

----

[[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется.

Классы BPP, BPPweak и BPPstrong

2012-06-04T20:09:00Z

Andrey.Eremeev: переименовал Классы BPP, BPPweak и BPPstrong в Классы BPP

#перенаправление [[Классы BPP]]

Классы BPP

2012-06-04T20:09:00Z

Andrey.Eremeev: переименовал Классы BPP, BPPweak и BPPstrong в Классы BPP

==Определения==
{{Определение
|definition =
<tex>\mathrm{BPP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых существует такая [[Вероятностные вычисления. Вероятностная машина Тьюринга |ВМТ]] <tex>p</tex>, что для любого <tex>x</tex>:
# <tex>P(p(x) = [x \in L]) \ge 2/3</tex>;
# <tex>T(p, x) \le poly(|x|)</tex> для любой [[Вероятностные вычисления. Вероятностная машина Тьюринга |вероятностной ленты]].
}}

<tex>\mathrm{BPP}</tex> — сложностный класс, допускающий двусторонние ошибки.
Константу <tex>2/3</tex> можно заменить на любое число из промежутка <tex>(1/2, 1)</tex>, так как требуемой вероятности можно добиться множественным запуском <tex>p</tex>. Замена константы на <tex>1/2</tex> сделала бы данный класс равным <tex>\Sigma^*</tex> (программа, возвращающая результат функции ''random''(), подошла бы для любого языка).

{{Определение
|definition=
<tex>\mathrm{BPP_{weak}}</tex> — класс языков <tex>L</tex>, для которых существует такая ВМТ <tex>p</tex>, что для любого <tex>x</tex>:
#<tex>P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(|x|)}</tex>, где <tex>q</tex>-полином и <tex>q(|x|) \ge 3</tex>;
#<tex>T(p, x) \le poly(|x|)</tex> для любой вероятностной ленты.
}}

{{Определение
|definition=
<tex>\mathrm{BPP_{strong}}</tex> — класс языков <tex>L</tex>, для которых существует такая ВМТ <tex>p</tex>, что для любого <tex>x</tex>:
#<tex>P(p(x)=[x \in L]) \ge 1 - \frac {1} {2^{q(|x|)}}</tex>, где <tex>q</tex>-полином и <tex>q(|x|) \ge 3</tex>;
#<tex>T(p, x) \le poly(|x|)</tex> для любой вероятностной ленты.
}}

==Теорема==
{{Теорема
|statement= <tex>\mathrm{BPP} = \mathrm{BPP_{weak}} = \mathrm{BPP_{strong}}</tex>.
|proof=
В доказательстве будет использоваться ''неравенство Чернова'': 
<tex>\forall p : \frac {1} {2} \le p \le 1: \sum\limits_{i = \lfloor \frac{n}{2} \rfloor + 1}^n \binom{n}{i}p^i (1 - p)^{n - i} \ge 1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2}</tex>

* Докажем, что <tex>\mathrm{BPP} = \mathrm{BPP_{weak}}</tex>
# <tex>\mathrm{BPP} \subseteq \mathrm{BPP_{weak}}</tex> Это следует из определений <tex>\mathrm{BPP}</tex> и <tex>\mathrm{BPP_{weak}}</tex>.
# <tex>\mathrm{BPP_{weak}} \subseteq \mathrm{BPP}</tex> Пусть <tex>L \in \mathrm{BPP_{weak}}</tex>. Тогда <tex>\exists p : P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(|x|)}</tex>. Построим ВМТ <tex>p_1</tex>, которая для входа <tex>x</tex> запускает <tex>p(x)</tex> <tex>n</tex> раз, и принимает <tex>x</tex>, если больше половины запусков принимают его. Подберем <tex>n</tex>, такое, что <tex>P(p_1(x)=[x \in L]) \ge \frac {2}{3}</tex> и <tex>T(p_1(x)) \le poly(|x|)</tex>. Вероятность <tex>P</tex> того, что <tex>p_1(x)</tex> даст правильный результат равна вероятности, что больше половины запусков <tex>p(x)</tex> дадут правильный результат. Тогда по схеме Бернулли <tex>P = \sum\limits_{i = \lfloor \frac{n}{2} \rfloor + 1}^n \binom{n}{i}p^i (1 - p)^{n - i}</tex>, где <tex>p=\frac {1}{2} + \frac {1} {q(|x|)}</tex> — вероятность, что запуск <tex>p(x)</tex> даст правильный ответ. По неравенству Чернова : <tex> P \ge 1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} </tex>. То есть для того, чтобы <tex>P(p(x)=[x \in L]) \ge \frac {2}{3}</tex> достаточно подобрать такое <tex>n</tex>, что <tex>1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} \ge \frac {2}{3}</tex>. Получаем, что <tex>n \ge \frac {\ln 3} {2(p - \frac {1} {2})^2} = \frac {{q(|x|)}^2 \ln 3}{2} </tex>. Возьмем <tex>n = \lceil \frac {{q(|x|)}^2 \ln 3}{2} \rceil </tex>, тогда неравенство <tex>T(p_1(x)) \le poly(|x|)</tex> будет выполнено.

* Докажем, что <tex>\mathrm{BPP} = \mathrm{BPP_{strong}}</tex>
# <tex>\mathrm{BPP_{strong}} \subseteq \mathrm{BPP} </tex> Это следует из определений <tex>\mathrm{BPP}</tex> и <tex>\mathrm{BPP_{strong}}</tex>.
# <tex>\mathrm{BPP} \subseteq \mathrm{BPP_{strong}}</tex> Пусть <tex>L \in \mathrm{BPP}</tex>. Тогда <tex>\exists p : P(p(x)=[x \in L]) \ge \frac {2}{3}</tex>. Построим ВМТ <tex>p_1</tex>, которая для входа <tex>x</tex> запускает <tex>p(x)</tex> <tex>n</tex> раз, и принимает <tex>x</tex>, если больше половины запусков принимают его. Подберем <tex>n</tex>, такое, что <tex>P(p_1(x)=[x \in L]) \ge 1 - \frac {1}{2^{q(|x|)}}</tex> и <tex>T(p_1(x)) \le poly(|x|)</tex>. Проводя рассуждения, аналогичные изложенным в доказательстве <tex>\mathrm{BPP_{weak}} \subseteq \mathrm{BPP}</tex>, получаем, что <tex>1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} \ge 1 - \frac {1}{2^{q(|x|)}}</tex>, где <tex>p = \frac {2} {3}</tex>. Отсюда <tex>n \ge \frac {{q(|x|)} \ln 2}{2({\frac {2}{3} - \frac {1}{2}})^2} </tex>. Возьмем <tex>n = \lceil 18 {q(|x|)} \ln 2 \rceil </tex>, тогда неравенство <tex>T(p_1(x)) \le poly(|x|)</tex> будет выполнено.
}}

{{Теорема
|statement =
<tex>\mathrm{RP} \cup \mathrm{coRP} \subset \mathrm{BPP}</tex>.
|proof =
Пусть <tex>p</tex> — программа для <tex>L \in \mathrm{RP}</tex>. Программу <tex>q</tex> для <tex>\mathrm{BPP}</tex> определим следующим образом:
<tex>q</tex>(x)
u <- <tex>p</tex>(x)
v <- <tex>p</tex>(x)
'''return''' u '''or''' v
Пусть <tex>x \in L</tex>. В этом случае вероятность ошибки равна <tex>\operatorname{P}(u = 0, v = 0) = \operatorname{P}(u = 0) \cdot \operatorname{P}(v = 0) \le 1/4</tex>.

Пусть <tex>x \notin L</tex>. Тогда с вероятностью <tex>1</tex> будет верно <tex>u = 0, v = 0</tex> и <tex>q</tex> вернет правильный ответ.

Аналогично доказывается, что <tex>\mathrm{coRP} \subset \mathrm{BPP}</tex>.
}}

== См. также ==
* [[Вероятностные вычисления. Вероятностная машина Тьюринга]] 
* [http://en.wikipedia.org/wiki/Chernoff_bound Неравенство Чернова]

[[Категория: Теория сложности]]

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

2012-06-04T19:58:24Z

Andrey.Eremeev: /* См. также */

[[Категория: Теория сложности]]
'''Вероятностные вычисления''' — один из подходов в теории вычислительной сложности, в котором программы получают доступ, говоря неформально, к генератору случайных чисел. Мы рассмотрим классы сложности, для которых программы могут работать за полиномиальное время и делать односторонние, двусторонние ошибки или работать за полиномиальное время лишь в среднем случае.

== Основные определения ==
{{Определение
|definition =
'''Вероятностная лента''' — бесконечная в одну сторону последовательность битов, распределение которых подчиняется некоторому вероятностному закону (обычно считают, что биты в различных позициях независимы и вероятность нахождения <tex>0</tex> или <tex>1</tex> в каждой позиции равна <tex>1/2</tex>).
}}
{{Определение
|definition =
'''Вероятностная машина Тьюринга''' (ВМТ) — детерминированная машина Тьюринга, имеющая вероятностную ленту. Переходы в ВМТ могут осуществляться с учетом информации, считанной с вероятностной ленты.
}}

Используя тезис Черча-Тьюринга, ВМТ можно сопоставить программы, имеющие доступ к случайным битам. Обращение к очередному биту можно трактовать как вызов специальной функции ''random''(). При этом также будем предполагать, что вероятностная лента является неявным аргументом программы или ВМТ, т.е. <tex>p(x) = p(x, r)</tex>, где <tex>r</tex> — вероятностная лента.

Введем [http://ru.wikipedia.org/wiki/Вероятностное_пространство вероятностное пространство] <tex>(\Omega, \Sigma, \operatorname{P})</tex>, где пространство элементарных исходов <tex>\Omega</tex> — множество всех вероятностных лент, <tex>\Sigma</tex> — сигма-алгебра подмножеств <tex>\Omega</tex>, <tex>\operatorname{P}</tex> — вероятностная мера, заданная на <tex>\Sigma</tex>. Будем считать, что <tex>\Sigma</tex> порождена событиями, зависящими лишь от конечного числа бит вероятностной ленты (то есть существующими в дискретных вероятностных пространствах). Покажем, что любой предикат от ВМТ является событием.
{{Теорема
|statement= Пусть <tex>m</tex> — ВМТ. Тогда для любых <tex>x</tex> и <tex>A</tex> — предиката от <tex>m</tex> выполняется <tex>R = \{r \bigm| A(m(x, r))\} \in \Sigma</tex>, т.е. <tex>R</tex> измеримо.
|proof=
<tex>R = \bigcup\limits_{i = 0}^\infty R_i</tex>, где <tex>R_i = \{r \bigm| A(m(x, r)), m</tex> прочитала ровно <tex>i</tex> первых символов с <tex>r\}</tex>. Это верно, поскольку мы рассматриваем только завершающиеся ВМТ. Кроме того, из определения <tex>R_i</tex> следует, что они дизъюнктны.

<tex>R_i \in \Sigma</tex> как зависящие от <tex>i</tex> первых битов вероятностной ленты, <tex>\operatorname{P}(R_i) = \frac{1}{2^i} \cdot |\{s \bigm| |s| = i, s</tex> — префикс <tex>r \in R_i\}|</tex>.

<tex>R \in \Sigma</tex> как счетное объединение событий, при этом из их дизъюнктности следует, что <tex>\operatorname{P}(R) = \sum\limits_{i = 0}^{\infty} \operatorname{P}(R_i)</tex>.
}}

== Вероятностные классы сложности ==
{{Определение
|definition =
<tex>\mathrm{RP}</tex> (от ''randomized polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:
# <tex>x \notin L \Rightarrow \operatorname{P}(p(x) = 0) = 1</tex>; 
# <tex>x \in L \Rightarrow \operatorname{P}(p(x) = 1) \ge 1/2</tex>; 
# <tex>\forall r \operatorname{T}(p, x) \le poly(|x|).</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{PP}</tex> (от ''probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:
# <tex>\operatorname{P}(p(x) = [x \in L]) > 1/2</tex>;
# <tex>\forall r \operatorname{T}(p, x) \le poly(|x|)</tex>.
}}
<tex>\mathrm{PP}</tex> также допускает двусторонние ошибки, но является более широким по сравнению с <tex>\mathrm{BPP}</tex>.

== Соотношение вероятностных классов ==
{{Теорема
|statement = <tex>\mathrm{RP} \subset \mathrm{NP} \subset \mathrm{PP} \subset \mathrm{PS}</tex>.
|proof =
1. <tex>\mathrm{RP} \subset \mathrm{NP}</tex>. Если в программе для <tex>L \in \mathrm{RP}</tex> заменить все вызовы ''random''() на недетерминированный выбор, то получим программу для <tex>L</tex> с ограничениями <tex>\mathrm{NP}</tex>.

2. <tex>\mathrm{NP} \subset \mathrm{PP}</tex>. Приведем программу <tex>q</tex> с ограничениями класса <tex>\mathrm{PP}</tex>, которая разрешает <tex>L \in \mathrm{NP}</tex>. Пусть функция ''infair_coin''() моделирует нечестную монету, а именно возвращает единицу с вероятностью <tex>1/2 - \varepsilon</tex>, где <tex>\varepsilon</tex> мы определим позже, и ноль с вероятностью <tex>1/2 + \varepsilon</tex>. Пусть также <tex>V</tex> — верификатор сертификатов для <tex>L</tex>. Тогда <tex>q</tex> будет выглядеть следующим образом:
<tex>q</tex>(x)
c <- случайный сертификат
'''if''' <tex>V</tex>(x, c)
'''return''' 1
'''return''' infair_coin()
Необходимо удовлетворить условию <tex>\operatorname{P}(q(x) = [x \in L]) > 1/2</tex>.

Пусть <tex>x \notin L</tex>. В этом случае <tex>V(x, c)</tex> вернет <tex>0</tex> и результат работы программы будет зависеть от нечестной монеты. Она вернет <tex>0</tex> с вероятностью <tex>1/2 + \varepsilon > 1/2</tex>.

Пусть <tex>x \in L</tex>. Тогда [[Формула полной вероятности|по формуле полной вероятности]] <tex>\operatorname{P}(q(x) = 1) = p_0 + (1 - p_0) (1/2 - \varepsilon)</tex>, где <tex>p_0</tex> — вероятность угадать правильный сертификат. Заметим, что поскольку длина всех сертификатов ограничена некоторым полиномом <tex>s(n), n = |x|</tex> и существует хотя бы один правильный сертификат, <tex>p_0 \ge 2^{-s(n)}</tex>. Найдем <tex>\varepsilon</tex> из неравенства <tex>\operatorname{P}(q(x) = 1) > 1/2</tex>:

<tex>p_0 + 1/2 - \varepsilon - p_0 / 2 + p_0 \varepsilon > 1/2</tex>;

<tex>p_0 / 2 + (p_0 - 1)\varepsilon > 0</tex>;

<tex>\varepsilon < \frac{p_0}{2 (1 - p_0)}</tex>.

Достаточно взять <tex>\varepsilon \le p_0 / 2</tex>. Из сделанного выше замечания следует, что работу функции ''infair_coin''() можно смоделировать с помощью не более чем <tex>s(n) + 1</tex> вызовов ''random''(). Также учтем, что длина сертификата и время работы <tex>V</tex> полиномиальны относительно <tex>|x|</tex>. Таким образом, мы построили программу <tex>q</tex>, удовлетворяющую ограничениям класса <tex>\mathrm{PP}</tex>.

3. <tex>\mathrm{PP} \subset \mathrm{PS}</tex>. Пусть <tex>p</tex> — программа для языка <tex>L \in \mathrm{PP}</tex>. Она используют не более чем полиномиальное количество вероятностных бит, так как сама работает за полиномиальное время. Тогда программа для <tex>\mathrm{PS}</tex> будет перебирать все участки вероятностных лент нужной полиномиальной длины и запускать на них <tex>p</tex>. Ответом будет <tex>0</tex> или <tex>1</tex> в зависимости от того, каких ответов <tex>p</tex> оказалось больше.
}}

{{Теорема
|statement =
<tex>\mathrm{RP} \cup \mathrm{coRP} \subset \mathrm{BPP}</tex>.
|proof =
Пусть <tex>p</tex> — программа для <tex>L \in \mathrm{RP}</tex>. Программу <tex>q</tex> для <tex>\mathrm{BPP}</tex> определим следующим образом:
<tex>q</tex>(x)
u <- <tex>p</tex>(x)
v <- <tex>p</tex>(x)
'''return''' u '''or''' v
Пусть <tex>x \in L</tex>. В этом случае вероятность ошибки равна <tex>\operatorname{P}(u = 0, v = 0) = \operatorname{P}(u = 0) \cdot \operatorname{P}(v = 0) \le 1/4</tex>.

Пусть <tex>x \notin L</tex>. Тогда с вероятностью <tex>1</tex> будет верно <tex>u = 0, v = 0</tex> и <tex>q</tex> вернет правильный ответ.

Аналогично доказывается, что <tex>\mathrm{coRP} \subset \mathrm{BPP}</tex>.
}}

== См. также ==
* [[Теоремы о BPP, BPPweak и BPPstrong]]
* [[Классы RP и coRP]]
* [[Теорема Лаутемана]]

== Литература ==
* [http://www.cs.princeton.edu/theory/complexity/ Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach]

Теория сложности

2012-06-04T19:48:36Z

Andrey.Eremeev: /* Вероятностные сложностные классы */

{{В разработке}}

[[Категория: Теория сложности]]

== Детерминированные и недетерминированные вычисления, сложность по времени и по памяти ==
*[[Сложностные классы. Вычисления с оракулом]]

=== Классы P и NP, NP-полнота ===
*[[Класс P]]
*[[Недетерминированные вычисления]]
*[[Классы NP и Σ₁]]
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
*[[Примеры NP-полных языков. Теорема Кука]]
*[[Теоремы о временной и емкостной иерархиях]]
*[[Теорема Бейкера — Гилла — Соловэя]]
*[[Теорема Ладнера]]
*[[Теорема Левина]]
*[[Теорема Бермана — Форчуна]]
*[[Теорема Махэни]]

=== Сложность по памяти, классы PS, L, NL, coNL ===
*[[Класс PS. Связь класса PS с другими классами теории сложности]]
*[[Теорема Сэвича. Совпадение классов NPS и PS]]
*[[PS-полнота языка верных булевых формул с кванторами (TQBF)]]
*[[Классы L, NL, coNL]]
*[[NL-полнота задачи о достижимости]]
*[[Теорема Иммермана]]

=== Полиномиальная иерархия ===
*[[Классы PH, Σ и Π]]
*[[Теоремы о коллапсе полиномиальной иерархии]]

== Схемная сложность ==
*[[Схемная сложность и класс P/poly]]
*[[Теорема Карпа — Липтона]]
*[[Классы NC и AC]]
*[[Теорема о непринадлежности XOR классу AC⁰]]

== Вероятностные сложностные классы ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
*[[Классы RP и coRP]]
*[[Класс ZPP]]
*[[Класс BPP]]
*[[Классы BPPweak и BPPstrong]]
*[[Теорема Лаутемана]]

=== Интерактивные протоколы ===
*[[Интерактивные протоколы. Класс IP. Класс AM]]
*[[Связь классов IP и AM друг с другом и с другими классами языков]]
*[[Арифметизация булевых формул с кванторами]]
*[[Лемма о соотношении coNP и IP]]
*[[Теорема Шамира]]
*[[Семейство универсальных попарно независимых хеш-функций]]
*[[Протокол Голдвассера-Сипсера для оценки размера множества]]

=== Probabilistically checkable proofs ===
*[[PCP-система]]
*[[PCP-теорема]]
*[[PCP-теорема, альтернативное доказательство | PCP-теорема, альтернативная формулировка]]

----

[[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется.

Классы RP и coRP

2012-06-04T19:48:08Z

Andrey.Eremeev: переименовал Уменьшение ошибки в классе RP в Классы RP и coRP

== Определения ==
{{Определение
|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>.
}}

{{Определение
|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> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>p_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>p_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(p_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>p_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>p_{\mathrm{RP_{weak}}}</tex> меньше, чем <tex>1-\frac{1}{q(|x|)}</tex>, то есть вероятность ошибки программы <tex>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>. Логарифмируя, получаем <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство аналогично предыдущему пункту.
<tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Но здесь <tex>k</tex> выбирается так, чтобы выполнялось неравенство <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)}</tex>. 
То есть <tex>k > log_2(q(|x|))</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
Напишем программу <tex>p_{\mathrm{RP_{strong}}}</tex>, удолетворяющую ограничениям сложностного класса <tex>\mathrm{RP_{strong}}</tex>.
<tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
В этом случае <tex>k</tex> необходимо выбрать таким, что должно выполняться неравенство <tex>(\frac{1}{2})^k < 1 - \frac{1}{2^{q(|x|)}}</tex>. То есть <tex>k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. Разложив в ряд Тейлора получаем, что <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>. То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>.

<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство <tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>. Отсюда <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]

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Уменьшение ошибки в классе RP

2012-06-04T19:48:08Z

Andrey.Eremeev: переименовал Уменьшение ошибки в классе RP в Классы RP и coRP

#перенаправление [[Классы RP и coRP]]

Обсуждение:Классы RP и coRP

2012-06-04T19:48:08Z

Andrey.Eremeev: переименовал Обсуждение:Уменьшение ошибки в классе RP в Обсуждение:Классы RP и coRP

Обозначение "программа m" меня убивает. Если программа, то все-таки р, m - это МТ.
'''then''' на следующей строке в псевдокоде добивает контрольным выстрелом...
Алгебраически выкладки не стоит делать в середине текста, вынеси в отдельные строки, пожалуйста.
Точка, которая переносится на следующую строку в отрыве от формулы, меня печалит.

Самое интересное, по сути претензий вроде как и нет.

Обсуждение:Уменьшение ошибки в классе RP

2012-06-04T19:48:08Z

Andrey.Eremeev: переименовал Обсуждение:Уменьшение ошибки в классе RP в Обсуждение:Классы RP и coRP

#перенаправление [[Обсуждение:Классы RP и coRP]]

Классы RP и coRP

2012-06-04T19:22:29Z

Andrey.Eremeev:

Теоремы о коллапсе полиномиальной иерархии

2012-06-04T18:31:52Z

Andrey.Eremeev:

{{Лемма
|statement = Если <tex>\Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Pi_i = \Pi_{i+1}</tex>.
|proof = <tex>L \in \Pi_{i+1} \Leftrightarrow \overline{L} \in \Sigma_{i+1} \Leftrightarrow \overline{L} \in \Sigma_i \Leftrightarrow L \in \Pi_i</tex>.
}}

== Теорема о коллапсе полиномиальной иерархии при совпадении <tex>\Sigma_i</tex> и <tex>\Sigma_{i+1}</tex> ==
{{Теорема
|statement = Если существует <tex>i \colon \Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Sigma_i = \mathrm{PH}</tex>.
|proof = Для доказательства теоремы достаточно показать, что если такое <tex>i</tex> существует, то <tex>\forall j > i</tex> верно, что <tex>\Sigma_i = \Sigma_j</tex>. 
Докажем по индукции. 
'''База'''. <tex>\Sigma_i = \Sigma_{i+1}</tex> из условия. 
'''Индукционный переход'''. Докажем, что если <tex>\Sigma_n = \Sigma_{n+1}</tex>, то <tex>\Sigma_{n+1} = \Sigma_{n+2}</tex>. 
Рассмотрим язык <tex>L \in \Sigma_{n+2}</tex>. <tex>L = \{x \bigm| \exists y_1 \forall y_2 \ldots Q y_{n+2} R_L^{n+2}(x, y_1 \ldots y_{n+2})\}</tex>. Обозначим <tex>\forall y_2 \ldots Q y_{n+2} R_L^{n+2}(x, y_1 \ldots y_{n+2}) = f(x, y_1)</tex>.
Тогда получим язык <tex>L_f = \{\langle x, y_1\rangle \bigm| f(x, y_1) = 1\}</tex>. 
Заметим, что <tex>L_f \in \Pi_{n+1}</tex> и из вышедоказанной леммы следует, что <tex>L_f \in \Pi_n</tex>. 
Из определения сложностного класса <tex>\Pi_n</tex> получаем, что <tex>\exists R_{L_f}^{n} \colon \langle x, y_1 \rangle \in L_f \Leftrightarrow \forall y_2 \exists y_3 \ldots Q y_{n+1} R_{L_f}^{n}(\langle x, y_1\rangle, y_2 \ldots y_{n+1})</tex>. Следовательно, <tex>x \in L \Leftrightarrow \exists y_1 \forall y_2 \ldots Q y_{n+1} R_L^{n+1}(x, y_1, y_2 \ldots y_{n+1})</tex>.
<tex>R_L^{n+1}(x, y_1, y_2 \ldots y_{n+1})</tex>
'''return''' <tex>R_{L_f}^n(\langle x, y_1\rangle, y_2 \ldots y_{n+1})</tex>
То есть язык <tex>L \in \Sigma_{n+1}</tex>.
}}

== Теорема о коллапсе полиномиальной иерархии при совпадении <tex>\Sigma_i</tex> и <tex>\Pi_i</tex> ==
{{Теорема
|statement = Если существует <tex>i > 0\colon \Sigma_i = \Pi_i</tex>, то <tex>\Sigma_i = \mathrm{PH}</tex>.
|proof =
Для доказательства покажем, что <tex>\Sigma_i = \Sigma_{i+1}</tex>, и воспользуемся предыдущей теоремой.

Рассмотрим язык <tex>L \in \Sigma_{i+1}</tex>. <tex>L =\{x \bigm| \exists y_1 \forall y_2 \ldots Q y_{i+1} R_L^{i+1}(x, y_1 \ldots y_{i+1})\}</tex>. Обозначим <tex>\forall y_2 \exists y_3 \ldots Q y_{i+1} R_L^{i+1}(x, y_1 \ldots y_{i+1}) = f(x, y_1)</tex>. Получим язык <tex>L_f = \{ \langle x, y_1 \rangle \bigm| f(x, y_1) = 1\}</tex>. 
Тогда <tex>L_f \in \Pi_i</tex>, и из условия теоремы <tex>L_f \in \Sigma_i</tex>. 
По определению сложностного класса <tex>\Sigma_i \; \exists R_{L_f}^i \colon \langle x, y_1 \rangle \in L_f \Leftrightarrow \exists y_2 \forall y_3 \ldots Q y_{i+1} R_{L_f}^i(\langle x, y_1 \rangle, y_2 \ldots y_{i+1})</tex>. Тогда <tex>x \in L \Leftrightarrow \exists \langle y_1, y_2 \rangle \forall y_3 \ldots Q y_{i+1} R_L^i(x, \langle y_1, y_2\rangle \ldots y_{i+1})</tex>. 
<tex>R_L^i(x, \langle y_1, y_2\rangle, y_3 \ldots, y_{i+1})</tex>
'''return''' <tex>R_{L_f}^i(\langle x, y_1\rangle, y_2, y_3 \ldots y_{i+1})</tex>
Значит, <tex>L \in \Sigma_i</tex>.
}}
Заметим, что <tex>\Sigma_0 = \Pi_0 = \mathrm{P}</tex>, а потому формулировка теоремы не имеет смысла при <tex>i = 0</tex>.

== Литература ==
* S.Arora, B.Barak. The polynomial hierarchy and alternations. Cambridge University, January 2007. [http://www.cs.princeton.edu/theory/complexity/phchap.pdf]

[[Категория: Теория сложности]]

Теория сложности

2012-06-04T07:50:04Z

Andrey.Eremeev:

{{В разработке}}

[[Категория: Теория сложности]]

*[[Сложностные классы. Вычисления с оракулом]]
*[[Класс P]]
*[[Недетерминированные вычисления. Классы NP и Σ₁]]
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
*[[Примеры NP-полных языков. Теорема Кука]]
*[[Теоремы о временной и емкостной иерархиях]]
*[[Теорема Бейкера — Гилла — Соловэя]]
*[[Теорема Ладнера]]
*[[Теорема Левина]]
*[[Теорема Бермана — Форчуна]]
*[[Теорема Махэни]]
*[[Класс PS. Теорема Сэвича. Совпадение классов NPS и PS]]
*[[PS-полнота языка верных булевых формул с кванторами (TQBF)]]
*[[Классы L, NL, coNL. NL-полнота задачи о достижимости]]
*[[Классы PH, Σ и Π]]
*[[Теоремы о коллапсе полиномиальной иерархии]]
*[[Схемная сложность и класс P/poly]]
*[[Теорема Карпа — Липтона]]
*[[Классы NC и AC]]
*[[Теорема о непринадлежности XOR классу AC⁰]]
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
*[[Классы BPPweak и BPPstrong]]
*[[Уменьшение ошибки в классе RP]]
*[[Теорема Лаутемана]]
*[[Интерактивные протоколы. Класс IP. Класс AM]]
*[[Связь классов IP и AM друг с другом и с другими классами языков]]
*[[Арифметизация булевых формул с кванторами]]
*[[Лемма о соотношении coNP и IP]]
*[[Теорема Шамира]]
*[[Семейство универсальных попарно независимых хеш-функций]]
*[[Протокол Голдвассера-Сипсера для оценки размера множества]]
*[[PCP-система]]
*[[PCP-теорема]]
*[[PCP-теорема, альтернативное доказательство]]

----

[[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется.

Классы RP и coRP

2012-06-04T07:49:00Z

Andrey.Eremeev: переименовал Уменьшение ошибки в классе RP. Теорема о соотношении классов coRP и coNP в Уменьшение ошибки в классе RP поверх перенаправления

== Определения ==
{{Определение
|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>.
}}
{{Определение
|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> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>p_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>p_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(p_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>p_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>p_{\mathrm{RP_{weak}}}</tex> меньше, чем <tex>1-\frac{1}{q(|x|)}</tex>, то есть вероятность ошибки программы <tex>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>. Логарифмируя, получаем <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство аналогично предыдущему пункту.
<tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Но здесь <tex>k</tex> выбирается так, чтобы выполнялось неравенство <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)}</tex>. 
То есть <tex>k > log_2(q(|x|))</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
Напишем программу <tex>p_{\mathrm{RP_{strong}}}</tex>, удолетворяющую ограничениям сложностного класса <tex>\mathrm{RP_{strong}}</tex>.
<tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
В этом случае <tex>k</tex> необходимо выбрать таким, что должно выполняться неравенство <tex>(\frac{1}{2})^k < 1 - \frac{1}{2^{q(|x|)}}</tex>. То есть <tex>k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. Разложив в ряд Тейлора получаем, что <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>. То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>.

<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство <tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>. Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Уменьшение ошибки в классе RP. Теорема о соотношении классов coRP и coNP

2012-06-04T07:49:00Z

#перенаправление [[Уменьшение ошибки в классе RP]]

Обсуждение:Классы RP и coRP

2012-06-04T07:49:00Z

Andrey.Eremeev: переименовал Обсуждение:Уменьшение ошибки в классе RP. Теорема о соотношении классов coRP и coNP в [[Обсуждение:Уменьшение ошибки в классе RP]...

Обсуждение:Уменьшение ошибки в классе RP. Теорема о соотношении классов coRP и coNP

2012-06-04T07:49:00Z

#перенаправление [[Обсуждение:Уменьшение ошибки в классе RP]]

Классы RP и coRP

2012-06-03T11:33:48Z

Andrey.Eremeev: /* Теорема о соотношении классов \mathrm{coRP} и \Pi_1 */

== Определения ==
{{Определение
|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>.
}}
{{Определение
|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> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>p_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>p_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(p_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>p_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>p_{\mathrm{RP_{weak}}}</tex> меньше, чем <tex>1-\frac{1}{q(|x|)}</tex>, то есть вероятность ошибки программы <tex>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>. Логарифмируя, получаем <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство аналогично предыдущему пункту.
<tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Но здесь <tex>k</tex> выбирается так, чтобы выполнялось неравенство <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)}</tex>. 
То есть <tex>k > log_2(q(|x|))</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
Напишем программу <tex>p_{\mathrm{RP_{strong}}}</tex>, удолетворяющую ограничениям сложностного класса <tex>\mathrm{RP_{strong}}</tex>.
<tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
В этом случае <tex>k</tex> необходимо выбрать таким, что должно выполняться неравенство <tex>(\frac{1}{2})^k < 1 - \frac{1}{2^{q(|x|)}}</tex>. То есть <tex>k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. Разложив в ряд Тейлора получаем, что <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>. То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>.

<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство <tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>. Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
}}
== Теорема о соотношении классов coRP и coNP ==
{{Теорема
|statement = <tex>\mathrm{coRP} \subset \mathrm{coNP}</tex>.
|proof = Рассмотрим язык <tex>L \in \mathrm{coRP} \Leftrightarrow \overline{L} \in \mathrm{RP} \Rightarrow \overline{L} \in \mathrm{NP} \Leftrightarrow L \in \mathrm{coNP}</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Теория сложности

2012-06-03T11:32:32Z

Andrey.Eremeev:

{{В разработке}}

[[Категория: Теория сложности]]

*[[Сложностные классы. Вычисления с оракулом]]
*[[Класс P]]
*[[Недетерминированные вычисления. Классы NP и Σ₁]]
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
*[[Примеры NP-полных языков. Теорема Кука]]
*[[Теоремы о временной и емкостной иерархиях]]
*[[Теорема Бейкера — Гилла — Соловэя]]
*[[Теорема Ладнера]]
*[[Теорема Левина]]
*[[Теорема Бермана — Форчуна]]
*[[Теорема Махэни]]
*[[Класс PS. Теорема Сэвича. Совпадение классов NPS и PS]]
*[[PS-полнота языка верных булевых формул с кванторами (TQBF)]]
*[[Классы L, NL, coNL. NL-полнота задачи о достижимости]]
*[[Классы PH, Σ и Π]]
*[[Теоремы о коллапсе полиномиальной иерархии]]
*[[Схемная сложность и класс P/poly]]
*[[Теорема Карпа — Липтона]]
*[[Классы NC и AC]]
*[[Теорема о не принадлежности XOR классу AC⁰]]
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
*[[Классы BPPweak и BPPstrong]]
*[[Уменьшение ошибки в классе RP. Теорема о соотношении классов coRP и coNP]]
*[[Теорема Лаутемана]]
*[[Интерактивные протоколы. Класс IP. Класс AM]]
*[[Связь классов IP и AM друг с другом и с другими классами языков]]
*[[Арифметизация булевых формул с кванторами]]
*[[Лемма о соотношении coNP и IP]]
*[[Теорема Шамира]]
*[[Семейство универсальных попарно независимых хеш-функций]]
*[[Протокол Голдвассера-Сипсера для оценки размера множества]]
*[[PCP-система]]
*[[PCP-теорема, альтернативное доказательство]]

----

[[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется.

Классы RP и coRP

2012-06-03T11:29:05Z

Andrey.Eremeev: переименовал Уменьшение ошибки в классе RP в Уменьшение ошибки в классе RP. Теорема о соотношении классов coRP и coNP

== Определения ==
{{Определение
|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>.
}}
{{Определение
|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> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>p_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>p_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(p_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>p_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>p_{\mathrm{RP_{weak}}}</tex> меньше, чем <tex>1-\frac{1}{q(|x|)}</tex>, то есть вероятность ошибки программы <tex>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>. Логарифмируя, получаем <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство аналогично предыдущему пункту.
<tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Но здесь <tex>k</tex> выбирается так, чтобы выполнялось неравенство <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)}</tex>. 
То есть <tex>k > log_2(q(|x|))</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
Напишем программу <tex>p_{\mathrm{RP_{strong}}}</tex>, удолетворяющую ограничениям сложностного класса <tex>\mathrm{RP_{strong}}</tex>.
<tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
В этом случае <tex>k</tex> необходимо выбрать таким, что должно выполняться неравенство <tex>(\frac{1}{2})^k < 1 - \frac{1}{2^{q(|x|)}}</tex>. То есть <tex>k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. Разложив в ряд Тейлора получаем, что <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>. То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>.

<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство <tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>. Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
}}
== Теорема о соотношении классов <tex>\mathrm{coRP}</tex> и <tex>\Pi_1</tex> ==
{{Теорема
|statement = <tex>\mathrm{coRP} \subset \Pi_1</tex>.
|proof = Рассмотрим язык <tex>L \in \mathrm{coRP} \Leftrightarrow \overline{L} \in \mathrm{RP} \Rightarrow \overline{L} \in \mathrm{NP} \Leftrightarrow L \in \mathrm{coNP} = \Pi_1</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Обсуждение:Классы RP и coRP

2012-06-03T11:29:05Z

Andrey.Eremeev: переименовал Обсуждение:Уменьшение ошибки в классе RP в Обсуждение:Уменьшение ошибки в классе RP. Теорема о соотношении классов coRP и coNP

Классы RP и coRP

2012-06-03T10:38:37Z

Andrey.Eremeev: /* Теорема о соотношении классов \mathrm{coRP} и \Pi_1 */

== Определения ==
{{Определение
|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>.
}}
{{Определение
|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> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>p_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>p_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(p_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>p_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>p_{\mathrm{RP_{weak}}}</tex> меньше, чем <tex>1-\frac{1}{q(|x|)}</tex>, то есть вероятность ошибки программы <tex>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>. Логарифмируя, получаем <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство аналогично предыдущему пункту.
<tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Но здесь <tex>k</tex> выбирается так, чтобы выполнялось неравенство <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)}</tex>. 
То есть <tex>k > log_2(q(|x|))</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
Напишем программу <tex>p_{\mathrm{RP_{strong}}}</tex>, удолетворяющую ограничениям сложностного класса <tex>\mathrm{RP_{strong}}</tex>.
<tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
В этом случае <tex>k</tex> необходимо выбрать таким, что должно выполняться неравенство <tex>(\frac{1}{2})^k < 1 - \frac{1}{2^{q(|x|)}}</tex>. То есть <tex>k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. Разложив в ряд Тейлора получаем, что <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>. То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>.

<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство <tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>. Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
}}
== Теорема о соотношении классов <tex>\mathrm{coRP}</tex> и <tex>\Pi_1</tex> ==
{{Теорема
|statement = <tex>\mathrm{coRP} \subset \Pi_1</tex>.
|proof = Рассмотрим язык <tex>L \in \mathrm{coRP} \Leftrightarrow \overline{L} \in \mathrm{RP} \Rightarrow \overline{L} \in \mathrm{NP} \Leftrightarrow L \in \mathrm{coNP} = \Pi_1</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Классы RP и coRP

2012-06-03T10:34:09Z

Andrey.Eremeev:

== Определения ==
{{Определение
|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>.
}}
{{Определение
|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> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>p_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>p_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(p_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>p_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>p_{\mathrm{RP_{weak}}}</tex> меньше, чем <tex>1-\frac{1}{q(|x|)}</tex>, то есть вероятность ошибки программы <tex>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>. Логарифмируя, получаем <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство аналогично предыдущему пункту.
<tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Но здесь <tex>k</tex> выбирается так, чтобы выполнялось неравенство <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)}</tex>. 
То есть <tex>k > log_2(q(|x|))</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
Напишем программу <tex>p_{\mathrm{RP_{strong}}}</tex>, удолетворяющую ограничениям сложностного класса <tex>\mathrm{RP_{strong}}</tex>.
<tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
В этом случае <tex>k</tex> необходимо выбрать таким, что должно выполняться неравенство <tex>(\frac{1}{2})^k < 1 - \frac{1}{2^{q(|x|)}}</tex>. То есть <tex>k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. Разложив в ряд Тейлора получаем, что <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>. То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>.

<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство <tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>. Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
}}
== Теорема о соотношении классов <tex>\mathrm{coRP}</tex> и <tex>\Pi_1</tex> ==
{{Теорема
|statement = <tex>\mathrm{coRP} \subset \Pi_1</tex>.
|proof = <tex>L \in \mathrm{coRP} \Leftrightarrow \overline{L} \in \mathrm{RP} \Rightarrow \overline{L} \in \mathrm{NP} \Leftrightarrow L \in \mathrm{coNP} = \Pi_1</tex>.
}}
== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Классы RP и coRP

2012-06-03T09:35:34Z

Andrey.Eremeev: /* Определения */

== Определения ==
{{Определение
|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>.
}}
{{Определение
|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> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>p_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>p_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(p_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>p_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>p_{\mathrm{RP_{weak}}}</tex> меньше, чем <tex>1-\frac{1}{q(|x|)}</tex>, то есть вероятность ошибки программы <tex>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>. Логарифмируя, получаем <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство аналогично предыдущему пункту.
<tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Но здесь <tex>k</tex> выбирается так, чтобы выполнялось неравенство <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)}</tex>. 
То есть <tex>k > log_2(q(|x|))</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
Напишем программу <tex>p_{\mathrm{RP_{strong}}}</tex>, удолетворяющую ограничениям сложностного класса <tex>\mathrm{RP_{strong}}</tex>.
<tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
В этом случае <tex>k</tex> необходимо выбрать таким, что должно выполняться неравенство <tex>(\frac{1}{2})^k < 1 - \frac{1}{2^{q(|x|)}}</tex>. То есть <tex>k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. Разложив в ряд Тейлора получаем, что <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>. То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>.

<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство <tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>. Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Классы RP и coRP

2012-06-03T09:31:53Z

Andrey.Eremeev: /* Теорема об эквивалентности определений */

== Определения ==
{{Определение
|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>.
}}
{{Определение
|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> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>p_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>p_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(p_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>p_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>p_{\mathrm{RP_{weak}}}</tex> меньше, чем <tex>1-\frac{1}{q(|x|)}</tex>, то есть вероятность ошибки программы <tex>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>. Логарифмируя, получаем <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство аналогично предыдущему пункту.
<tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Но здесь <tex>k</tex> выбирается так, чтобы выполнялось неравенство <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)}</tex>. 
То есть <tex>k > log_2(q(|x|))</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
Напишем программу <tex>p_{\mathrm{RP_{strong}}}</tex>, удолетворяющую ограничениям сложностного класса <tex>\mathrm{RP_{strong}}</tex>.
<tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
В этом случае <tex>k</tex> необходимо выбрать таким, что должно выполняться неравенство <tex>(\frac{1}{2})^k < 1 - \frac{1}{2^{q(|x|)}}</tex>. То есть <tex>k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. Разложив в ряд Тейлора получаем, что <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>. То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>.

<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство <tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>. Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Классы RP и coRP

2012-06-03T08:27:36Z

Andrey.Eremeev: /* Определения */

== Определения ==
{{Определение
|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>.
}}
{{Определение
|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> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>p_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>p_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(p_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>p_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>p_{\mathrm{RP_{weak}}}</tex> меньше, чем <tex>1-\frac{1}{q(|x|)}</tex>, то есть вероятность ошибки программы <tex>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>. Логарифмируя, получаем <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство аналогично предыдущему пункту.
<tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Но здесь <tex>k</tex> выбирается так, чтобы выполнялось неравенство <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)}</tex>. 
То есть <tex>k > log_2(q(|x|))</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
Напишем программу <tex>p_{\mathrm{RP_{strong}}}</tex>, удолетворяющую ограничениям сложностного класса <tex>\mathrm{RP_{strong}}</tex>.
<tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
В этом случае <tex>k</tex> необходимо выбрать таким, что должно выполняться неравенство <tex>(\frac{1}{2})^k < 1 - \frac{1}{2^{q(|x|)}}</tex>. То есть <tex>k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. Разложив в ряд Тейлора получаем, что <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>. То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>.

<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство <tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>. Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Классы RP и coRP

2012-06-03T08:14:29Z

Andrey.Eremeev: /* Теорема об эквивалентности определений */

== Определения ==
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>p</tex>, которая работает за полиномиальное время для любой вероятностной ленты, и:
# <tex>x \notin L \Rightarrow P(p(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(p(x) = 1) \geq \frac{1}{2}</tex>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{weak}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>p</tex>, которая работает за полиномиальное время для любой вероятностной ленты, и:
# <tex>x \notin L \Rightarrow P(p(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(p(x) = 1) \geq \frac{1}{q(|x|)}</tex>, где <tex>q(|x|)</tex> — некоторый полином, <tex>q(|x|) \geq 1</tex>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{strong}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>p</tex>, которая работает за полиномиальное время для любой вероятностной ленты, и:
# <tex>x \notin L \Rightarrow P(p(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(p(x) = 1) \geq 1 - \frac{1}{2^{q(|x|)}}</tex>, где <tex>q(|x|)</tex> — некоторый полином.
}}

== Теорема об эквивалентности определений ==
{{Теорема
|statement=<tex>\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}</tex>
|proof=
<tex>\mathrm{RP_{weak}} \subset \mathrm{RP}\colon</tex> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>p_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>p_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(p_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>p_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>p_{\mathrm{RP_{weak}}}</tex> меньше, чем <tex>1-\frac{1}{q(|x|)}</tex>, то есть вероятность ошибки программы <tex>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>. Логарифмируя, получаем <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство аналогично предыдущему пункту.
<tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Но здесь <tex>k</tex> выбирается так, чтобы выполнялось неравенство <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)}</tex>. 
То есть <tex>k > log_2(q(|x|))</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
Напишем программу <tex>p_{\mathrm{RP_{strong}}}</tex>, удолетворяющую ограничениям сложностного класса <tex>\mathrm{RP_{strong}}</tex>.
<tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
В этом случае <tex>k</tex> необходимо выбрать таким, что должно выполняться неравенство <tex>(\frac{1}{2})^k < 1 - \frac{1}{2^{q(|x|)}}</tex>. То есть <tex>k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. Разложив в ряд Тейлора получаем, что <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>. То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>.

<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство <tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>. Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Классы RP и coRP

2012-06-03T08:10:54Z

Andrey.Eremeev:

== Определения ==
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>p</tex>, которая работает за полиномиальное время для любой вероятностной ленты, и:
# <tex>x \notin L \Rightarrow P(p(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(p(x) = 1) \geq \frac{1}{2}</tex>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{weak}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>p</tex>, которая работает за полиномиальное время для любой вероятностной ленты, и:
# <tex>x \notin L \Rightarrow P(p(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(p(x) = 1) \geq \frac{1}{q(|x|)}</tex>, где <tex>q(|x|)</tex> — некоторый полином, <tex>q(|x|) \geq 1</tex>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{strong}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>p</tex>, которая работает за полиномиальное время для любой вероятностной ленты, и:
# <tex>x \notin L \Rightarrow P(p(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(p(x) = 1) \geq 1 - \frac{1}{2^{q(|x|)}}</tex>, где <tex>q(|x|)</tex> — некоторый полином.
}}

== Теорема об эквивалентности определений ==
{{Теорема
|statement=<tex>\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}</tex>
|proof=
<tex>\mathrm{RP_{weak}} \subset \mathrm{RP}\colon</tex> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>p_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{weak}}}(x)</tex> '''then'''
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>p_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(p_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>p_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>p_{\mathrm{RP_{weak}}}</tex> меньше, чем <tex>1-\frac{1}{q(|x|)}</tex>, то есть вероятность ошибки программы <tex>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>. Логарифмируя, получаем <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство аналогично предыдущему пункту.
<tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex> '''then'''
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Но здесь <tex>k</tex> выбирается так, чтобы выполнялось неравенство <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)}</tex>. 
То есть <tex>k > log_2(q(|x|))</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
Напишем программу <tex>p_{\mathrm{RP_{strong}}}</tex>, удолетворяющую ограничениям сложностного класса <tex>\mathrm{RP_{strong}}</tex>.
<tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>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|)}}</tex>. То есть <tex>k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. Разложив в ряд Тейлора получаем, что <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>. То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>.

<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{strong}}}(x)</tex> '''then'''
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство <tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>. Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Классы RP и coRP

2012-06-03T07:54:38Z

Andrey.Eremeev: /* Теорема об эквивалентности определений */

== Определения ==
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>p</tex>, которая работает за полиномиальное время, и:
# <tex>x \notin L \Rightarrow P(p(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(p(x) = 1) \geq \frac{1}{2}</tex>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{weak}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>p</tex>, которая работает за полиномиальное время, и:
# <tex>x \notin L \Rightarrow P(p(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(p(x) = 1) \geq \frac{1}{q(|x|)}</tex>, где <tex>q(|x|)</tex> — некоторый полином, <tex>q(|x|) \geq 1</tex>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{strong}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>p</tex>, которая работает за полиномиальное время, и:
# <tex>x \notin L \Rightarrow P(p(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(p(x) = 1) \geq 1 - \frac{1}{2^{q(|x|)}}</tex>, где <tex>q(|x|)</tex> — некоторый полином.
}}

== Теорема об эквивалентности определений ==
{{Теорема
|statement=<tex>\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}</tex>
|proof=
<tex>\mathrm{RP_{weak}} \subset \mathrm{RP}\colon</tex> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>p_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{weak}}}(x)</tex> '''then'''
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>p_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(p_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>p_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>p_{\mathrm{RP_{weak}}}</tex> меньше, чем <tex>1-\frac{1}{q(|x|)}</tex>, то есть вероятность ошибки программы <tex>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>. Логарифмируя, получаем <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство аналогично предыдущему пункту.
<tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex> '''then'''
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Но здесь <tex>k</tex> выбирается так, чтобы выполнялось неравенство <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)}</tex>. 
То есть <tex>k > log_2(q(|x|))</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
Напишем программу <tex>p_{\mathrm{RP_{strong}}}</tex>, удолетворяющую ограничениям сложностного класса <tex>\mathrm{RP_{strong}}</tex>.
<tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>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|)}}</tex>. То есть <tex>k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. Разложив в ряд Тейлора получаем, что <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>. То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>.

<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{strong}}}(x)</tex> '''then'''
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство <tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>. Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Классы RP и coRP

2012-06-03T07:07:59Z

Andrey.Eremeev: /* Теорема об эквивалентности определений */

== Определения ==
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>p</tex>, которая работает за полиномиальное время, и:
# <tex>x \notin L \Rightarrow P(p(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(p(x) = 1) \geq \frac{1}{2}</tex>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{weak}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>p</tex>, которая работает за полиномиальное время, и:
# <tex>x \notin L \Rightarrow P(p(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(p(x) = 1) \geq \frac{1}{q(|x|)}</tex>, где <tex>q(|x|)</tex> — некоторый полином, <tex>q(|x|) \geq 1</tex>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{strong}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>p</tex>, которая работает за полиномиальное время, и:
# <tex>x \notin L \Rightarrow P(p(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(p(x) = 1) \geq 1 - \frac{1}{2^{q(|x|)}}</tex>, где <tex>q(|x|)</tex> — некоторый полином.
}}

== Теорема об эквивалентности определений ==
{{Теорема
|statement=<tex>\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}</tex>
|proof=
<tex>\mathrm{RP_{weak}} \subset \mathrm{RP}\colon</tex> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>p_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{weak}}}(x)</tex> '''then'''
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>p_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(p_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>p_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>p_{\mathrm{RP_{weak}}}</tex> меньше, чем <tex>1-\frac{1}{q(|x|)}</tex>, то есть вероятность ошибки программы <tex>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>. Логарифмируя, получаем: <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство аналогично предыдущему пункту.
<tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex> '''then'''
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Но здесь <tex>k</tex> выбирается так, чтобы выполнялось неравенство <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)} \Leftrightarrow k > log_2(q(|x|))</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
Напишем программу <tex>m_{\mathrm{RP_{strong}}}</tex>, удолетворяющую ограничениям сложностного класса <tex>\mathrm{RP_{strong}}</tex>.
<tex>m_{\mathrm{RP_{strong}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>m_{\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 k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. Разложив в ряд Тейлора получаем, что <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>. То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>.

<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Для доказательства утверждения необходимо написать программу <tex>m_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>m_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>m_{\mathrm{RP_{strong}}}(x)</tex>
'''then return''' <tex>1</tex>
'''return''' <tex>0</tex>
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство <tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>. Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Классы RP и coRP

2012-06-03T06:59:30Z

Andrey.Eremeev: /* Определения */

== Определения ==
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>p</tex>, которая работает за полиномиальное время, и:
# <tex>x \notin L \Rightarrow P(p(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(p(x) = 1) \geq \frac{1}{2}</tex>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{weak}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>p</tex>, которая работает за полиномиальное время, и:
# <tex>x \notin L \Rightarrow P(p(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(p(x) = 1) \geq \frac{1}{q(|x|)}</tex>, где <tex>q(|x|)</tex> — некоторый полином, <tex>q(|x|) \geq 1</tex>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{strong}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>p</tex>, которая работает за полиномиальное время, и:
# <tex>x \notin L \Rightarrow P(p(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(p(x) = 1) \geq 1 - \frac{1}{2^{q(|x|)}}</tex>, где <tex>q(|x|)</tex> — некоторый полином.
}}

== Теорема об эквивалентности определений ==
{{Теорема
|statement=<tex>\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}</tex>
|proof=
<tex>\mathrm{RP_{weak}} \subset \mathrm{RP}\colon</tex> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>m_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>m_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>m_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>m_{\mathrm{RP_{weak}}}(x)</tex>
'''then return''' <tex>1</tex>
'''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>m_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(m_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>m_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>m_{\mathrm{RP_{weak}}}</tex> равна <tex>1-\frac{1}{q(|x|)}</tex>, то есть вероятность ошибки программы <tex>m_{\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>. Логарифмируя, получаем: <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство аналогично предыдущему пункту.
<tex>m_{\mathrm{RP_{weak}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>m_{\mathrm{RP}}(x)</tex>
'''then return''' <tex>1</tex>
'''return''' <tex>0</tex>
Но здесь <tex>k</tex> выбирается так, чтобы выполнялось неравенство <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)}</tex>. Из него получается, что <tex>k > log_2(q(|x|))</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
Напишем программу <tex>m_{\mathrm{RP_{strong}}}</tex>, удолетворяющую ограничениям сложностного класса <tex>\mathrm{RP_{strong}}</tex>.
<tex>m_{\mathrm{RP_{strong}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>m_{\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 k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. Разложив в ряд Тейлора получаем, что <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>. То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>.

<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Для доказательства утверждения необходимо написать программу <tex>m_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>m_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>m_{\mathrm{RP_{strong}}}(x)</tex>
'''then return''' <tex>1</tex>
'''return''' <tex>0</tex>
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство <tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>. Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Классы RP и coRP

2012-05-30T17:08:57Z

Andrey.Eremeev: /* Определения */

== Определения ==
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</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>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{weak}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</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>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{strong}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</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> — некоторый полином.
}}

== Теорема об эквивалентности определений ==
{{Теорема
|statement=<tex>\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}</tex>
|proof=
<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Рассмотрим язык <tex>L \in \mathrm{RP_{strong}}</tex>. Этому языку соответсвует программа <tex>m_{\mathrm{RP_{strong}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>m_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>. В качестве программы <tex>m_{\mathrm{RP}}</tex> можно взять программу <tex>m_{\mathrm{RP_{strong}}}</tex>, так как <tex>1 - \frac{1}{2^p} \geq \frac{1}{2} \Leftrightarrow p \geq 1</tex>. То есть программа <tex>m_{\mathrm{RP_{strong}}}</tex> удолетворяет ограничениям сложностного класса <tex>\mathrm{RP}</tex>. 
<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство такое же, как в предыдущем пункте. 
<tex>\mathrm{RP_{weak}} \subset \mathrm{RP}\colon</tex> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>m_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>m_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>m_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>m_{\mathrm{RP_{weak}}}(x)</tex>
'''then return''' <tex>1</tex>
'''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>m_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(m_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>m_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>m_{\mathrm{RP}}</tex> равна <tex>(1-\frac{1}{q(|x|)})^k</tex>, то есть программа <tex>m_{\mathrm{RP_{weak}}}</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>. Логарифмируя, получаем: <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>. 
<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
Доказательство аналогично предыдущему пункту. В этом случае <tex>k</tex> необходимо выбрать таким, что должно выполняться неравенство <tex>(\frac{1}{2})^k < 1 - \frac{1}{2^{q(|x|)}} \Leftrightarrow k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. Разложив в ряд Тейлора получаем, что <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>. То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Классы RP и coRP

2012-05-23T20:01:31Z

Andrey.Eremeev: /* Теорема об эквивалентности определений */

== Определения ==
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</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>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{weak}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</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>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{strong}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</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>q(|x|) \geq 1</tex>.
}}
== Теорема об эквивалентности определений ==
{{Теорема
|statement=<tex>\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}</tex>
|proof=
<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Рассмотрим язык <tex>L \in \mathrm{RP_{strong}}</tex>. Этому языку соответсвует программа <tex>m_{\mathrm{RP_{strong}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>m_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>. В качестве программы <tex>m_{\mathrm{RP}}</tex> можно взять программу <tex>m_{\mathrm{RP_{strong}}}</tex>, так как <tex>1 - \frac{1}{2^p} \geq \frac{1}{2} \Leftrightarrow p \geq 1</tex>. То есть программа <tex>m_{\mathrm{RP_{strong}}}</tex> удолетворяет ограничениям сложностного класса <tex>\mathrm{RP}</tex>. 
<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство такое же, как в предыдущем пункте. 
<tex>\mathrm{RP_{weak}} \subset \mathrm{RP}\colon</tex> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>m_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>m_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>m_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>m_{\mathrm{RP_{weak}}}(x)</tex>
'''then return''' <tex>1</tex>
'''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>m_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(m_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>m_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>m_{\mathrm{RP}}</tex> равна <tex>(1-\frac{1}{q(|x|)})^k</tex>, то есть программа <tex>m_{\mathrm{RP_{weak}}}</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>. Логарифмируя, получаем: <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>. 
<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
Доказательство аналогично предыдущему пункту. В этом случае <tex>k</tex> необходимо выбрать таким, что должно выполняться неравенство <tex>(\frac{1}{2})^k < 1 - \frac{1}{2^{q(|x|)}} \Leftrightarrow k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. Разложив в ряд Тейлора получаем, что <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>. То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Классы RP и coRP

2012-05-23T19:45:13Z

Andrey.Eremeev: /* Теорема об эквивалентности определений */

== Определения ==
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</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>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{weak}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</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>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{strong}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</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>q(|x|) \geq 1</tex>.
}}
== Теорема об эквивалентности определений ==
{{Теорема
|statement=<tex>\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}</tex>
|proof=
<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Рассмотрим язык <tex>L \in \mathrm{RP_{strong}}</tex>. Этому языку соответсвует программа <tex>m_{\mathrm{RP_{strong}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>m_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>. В качестве программы <tex>m_{\mathrm{RP}}</tex> можно взять программу <tex>m_{\mathrm{RP_{strong}}}</tex>, так как <tex>1 - \frac{1}{2^p} \geq \frac{1}{2} \Leftrightarrow p \geq 1</tex>. То есть программа <tex>m_{\mathrm{RP_{strong}}}</tex> удолетворяет ограничениям сложностного класса <tex>\mathrm{RP}</tex>. 
<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство такое же, как в предыдущем пункте. 
<tex>\mathrm{RP_{weak}} \subset \mathrm{RP}\colon</tex> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>m_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>m_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>m_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>m_{\mathrm{RP_{weak}}}(x)</tex>
'''then return''' <tex>1</tex>
'''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>m_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(m_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>m_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>m_{\mathrm{RP}}</tex> равна <tex>(1-\frac{1}{q(|x|)})^k</tex>, то есть программа <tex>m_{\mathrm{RP_{weak}}}</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>. Логарифмируя, получаем: <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>. 
<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
Доказательство аналогично предыдущему пункту. В этом случае <tex>k</tex> необходимо выбрать таким, что должно выполняться неравенство <tex>(\frac{1}{2})^k < 1 - \frac{1}{2^{q(|x|)}} \Leftrightarrow k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. Разложив в ряд Тейлора получаем, что <tex>-log_{2}(1-\frac{1}{2^{q(|x|)}}) = \frac{1}{ln(2)2^{q(|x|)}} = \frac{(1+q(|x|))^{ln(\frac{1}{2})}}{ln(2)} < \frac{1+q(|x|)}{ln(2)}</tex>. То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Классы RP и coRP

2012-05-23T19:18:21Z

Andrey.Eremeev: /* Теорема об эквивалентности определений */

== Определения ==
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</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>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{weak}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</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>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{strong}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</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>q(|x|) \geq 1</tex>.
}}
== Теорема об эквивалентности определений ==
{{Теорема
|statement=<tex>\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}</tex>
|proof=
<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Рассмотрим язык <tex>L \in \mathrm{RP_{strong}}</tex>. Этому языку соответсвует программа <tex>m_{\mathrm{RP_{strong}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>m_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>. В качестве программы <tex>m_{\mathrm{RP}}</tex> можно взять программу <tex>m_{\mathrm{RP_{strong}}}</tex>, так как <tex>1 - \frac{1}{2^p} \geq \frac{1}{2} \Leftrightarrow p \geq 1</tex>. То есть программа <tex>m_{\mathrm{RP_{strong}}}</tex> удолетворяет ограничениям сложностного класса <tex>\mathrm{RP}</tex>. 
<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство такое же, как в предыдущем пункте. 
<tex>\mathrm{RP_{weak}} \subset \mathrm{RP}\colon</tex> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>m_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>m_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>m_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>m_{\mathrm{RP_{weak}}}(x)</tex>
'''then return''' <tex>1</tex>
'''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>m_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(m_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>m_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>m_{\mathrm{RP}}</tex> равна <tex>(1-\frac{1}{q(|x|)})^k</tex>, то есть программа <tex>m_{\mathrm{RP_{weak}}}</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>. Логарифмируя, получаем: <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>. 
<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
Доказательство аналогично предыдущему пункту. В этом случае <tex>k</tex> необходимо выбрать таким, что должно выполняться неравенство <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)}</tex>. Прологарифмировав и сократив на <tex>ln(\frac{1}{2})</tex>, получаем, что <tex>k > q(|x|)</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Классы RP и coRP

2012-05-23T17:18:17Z

Andrey.Eremeev: /* Теорема об эквивалентности определений */

== Определения ==
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</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>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{weak}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</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>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{strong}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</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>q(|x|) \geq 1</tex>.
}}
== Теорема об эквивалентности определений ==
{{Теорема
|statement=<tex>\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}</tex>
|proof=
<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Рассмотрим язык <tex>L \in \mathrm{RP_{strong}}</tex>. Этому языку соответсвует программа <tex>m_{\mathrm{RP_{strong}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>m_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>. В качестве программы <tex>m_{\mathrm{RP}}</tex> можно взять программу <tex>m_{\mathrm{RP_{strong}}}</tex>, так как <tex>1 - \frac{1}{2^p} \geq \frac{1}{2} \Leftrightarrow p \geq 1</tex>. То есть программа <tex>m_{\mathrm{RP_{strong}}}</tex> удолетворяет ограничениям сложностного класса <tex>\mathrm{RP}</tex>. 
<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство такое же, как в предыдущем пункте. 
<tex>\mathrm{RP_{weak}} \subset \mathrm{RP}\colon</tex> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>m_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>m_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>m_{\mathrm{RP}}(x)</tex>
<tex>f = 0</tex> // столько раз программа <tex>m_{\mathrm{RP_{weak}}}</tex> вернула <tex>false</tex>
<tex>t = 0</tex> // столько раз программа <tex>m_{\mathrm{RP_{weak}}}</tex> вернула <tex>true</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>m_{\mathrm{RP_{weak}}}(x)</tex>
'''then''' <tex>f = f + 1</tex>
'''else''' <tex>t = t + 1</tex>
'''return''' <tex>f > t \ ? \ false : true</tex>
Если слово <tex>x \notin L</tex>, то <tex>m_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>false</tex>. Тогда <tex>P(m_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</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</tex>. Получается неравенство <tex>(1-\frac{1}{q(|x|)})^k < \frac{1}{2}</tex>. Логарифмируя, получаем: <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>. 
<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
Доказательство аналогично предыдущему пункту. В этом случае <tex>k</tex> необходимо выбрать таким, что должно выполняться неравенство <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)}</tex>. Прологарифмировав и сократив на <tex>ln(\frac{1}{2})</tex>, получаем, что <tex>k > q(|x|)</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Классы RP и coRP

2012-05-23T16:59:31Z

Andrey.Eremeev: /* Теорема об эквивалентности определений */

== Определения ==
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</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>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{weak}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</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>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{strong}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</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>q(|x|) \geq 1</tex>.
}}
== Теорема об эквивалентности определений ==
{{Теорема
|statement=<tex>\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}</tex>
|proof=
<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Рассмотрим язык <tex>L \in \mathrm{RP_{strong}}</tex>. Этому языку соответсвует программа <tex>m_{\mathrm{RP_{strong}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>m_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>. В качестве программы <tex>m_{\mathrm{RP}}</tex> можно взять программу <tex>m_{\mathrm{RP_{strong}}}</tex>, так как <tex>1 - \frac{1}{2^p} \geq \frac{1}{2} \Leftrightarrow p \geq 1</tex>. То есть программа <tex>m_{\mathrm{RP_{strong}}}</tex> удолетворяет ограничениям сложностного класса <tex>\mathrm{RP}</tex>. 
<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство такое же, как в предыдущем пункте. 
<tex>\mathrm{RP_{weak}} \subset \mathrm{RP}\colon</tex> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>m_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>m_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>m_{\mathrm{RP}}(x)</tex>
<tex>f = 0</tex> // столько раз программа <tex>m_{\mathrm{RP_{weak}}}</tex> вернула <tex>false</tex>
<tex>t = 0</tex> // столько раз программа <tex>m_{\mathrm{RP_{weak}}}</tex> вернула <tex>true</tex>
'''for''' <tex>i = 1 \ldots k</tex>
'''if''' <tex>m_{\mathrm{RP_{weak}}}(x)</tex>
'''then''' <tex>f = f + 1</tex>
'''else''' <tex>t = t + 1</tex>
'''return''' <tex>f > t \ ? \ false : true</tex>
Если слово <tex>x \notin L</tex>, то <tex>m_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>false</tex>. Тогда <tex>P(m_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. <tex>k</tex> надо выбрать таким, что вероятность ошибки программы <tex>m_{\mathrm{RP}}(x)</tex> при <tex>x \in L</tex> была меньше <tex>\frac {1}{2}</tex>. Вероятность ошибки программы равна <tex>(1-\frac{1}{q(|x|)})^k</tex>. Получается неравенство <tex>(1-\frac{1}{q(|x|)})^k < \frac{1}{2}</tex>. Логарифмируя, получаем: <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>.
<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Классы RP и coRP

2012-05-23T16:05:54Z

Andrey.Eremeev: /* Теорема об эквивалентности определений */

Классы RP и coRP

2012-05-23T15:20:31Z

Andrey.Eremeev:

Классы RP и coRP

2012-05-23T14:46:46Z

Andrey.Eremeev: /* Определения */

Классы RP и coRP

2012-05-23T14:21:15Z

Andrey.Eremeev: Новая страница: «== Определения == {{Определение |definition= Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>...»

Теоремы о коллапсе полиномиальной иерархии

2012-05-10T16:27:22Z

Andrey.Eremeev: /* Теорема о коллапсе полиномиальной иерархии при совпадении \Sigma_i и \Pi_i */

{{Лемма
|statement = Если <tex>\Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Pi_i = \Pi_{i+1}</tex>.
|proof = <tex>L \in \Pi_{i+1} \Leftrightarrow \overline{L} \in \Sigma_{i+1} \Leftrightarrow \overline{L} \in \Sigma_i \Leftrightarrow L \in \Pi_i</tex>.
}}

== Теорема о коллапсе полиномиальной иерархии при совпадении <tex>\Sigma_i</tex> и <tex>\Sigma_{i+1}</tex> ==
{{Теорема
|statement = Если существует <tex>i \colon \Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Sigma_i = PH</tex>.
|proof = Для доказательства теоремы достаточно показать, что если такое <tex>i</tex> существует, то <tex>\forall j > i</tex> верно, что <tex>\Sigma_i = \Sigma_j</tex>. 
Докажем по индукции. 
'''База'''. <tex>\Sigma_i = \Sigma_{i+1}</tex> из условия. 
'''Индукционный переход'''. Докажем, что если <tex>\Sigma_n = \Sigma_{n+1}</tex>, то <tex>\Sigma_{n+1} = \Sigma_{n+2}</tex>. 
Рассмотрим язык <tex>L \in \Sigma_{n+2}</tex>. <tex>L = \{x \colon \exists y_1 \forall y_2 \ldots Q y_{n+2} R_L^{n+2}(x, y_1 \ldots y_{n+2})\}</tex>. Обозначим <tex>\forall y_2 \ldots Q y_{n+2} R_L^{n+2}(x, y_1 \ldots y_{n+2}) = f(x, y_1)</tex>.
Тогда получим язык <tex>L_f = \{\langle x, y_1\rangle \colon f(x, y_1) = 1\}</tex>. 
Заметим, что <tex>L_f \in \Pi_{n+1}</tex> и из вышедоказанной леммы следует, что <tex>L_f \in \Pi_n</tex>. 
Из определения сложностного класса <tex>\Pi_n</tex> получаем, что <tex>\exists R_{L_f}^{n} \colon \langle x, y_1 \rangle \in L_f \Leftrightarrow \forall y_2 \exists y_3 \ldots Q y_{n+1} R_{L_f}^{n}(\langle x, y_1\rangle, y_2 \ldots y_{n+1})</tex>. Следовательно, <tex>x \in L \Leftrightarrow \exists y_1 \forall y_2 \ldots Q y_{n+1} R_L^{n+1}(x, y_1, y_2 \ldots y_{n+1})</tex>.
<tex>R_L^{n+1}(x, y_1, y_2 \ldots y_{n+1})</tex>
'''return''' <tex>R_{L_f}^n(\langle x, y_1\rangle, y_2 \ldots y_{n+1})</tex>
То есть язык <tex>L \in \Sigma_{n+1}</tex>.
}}

== Теорема о коллапсе полиномиальной иерархии при совпадении <tex>\Sigma_i</tex> и <tex>\Pi_i</tex> ==
{{Теорема
|statement = Если существует <tex>i > 0\colon \Sigma_i = \Pi_i</tex>, то <tex>\Sigma_i = PH</tex>.
|proof =
Для доказательства покажем, что <tex>\Sigma_i = \Sigma_{i+1}</tex>, и воспользуемся предыдущей теоремой.

Рассмотрим язык <tex>L \in \Sigma_{i+1}</tex>. <tex>L =\{x \colon \exists y_1 \forall y_2 \ldots Q y_{i+1} R_L^{i+1}(x, y_1 \ldots y_{i+1})\}</tex>. Обозначим <tex>\forall y_2 \exists y_3 \ldots Q y_{i+1} R_L^{i+1}(x, y_1 \ldots y_{i+1}) = f(x, y_1)</tex>. Получим язык <tex>L_f = \{ \langle x, y_1 \rangle \colon f(x, y_1) = 1\}</tex>. 
Тогда <tex>L_f \in \Pi_i</tex>, и из условия теоремы <tex>L_f \in \Sigma_i</tex>. 
По определению сложностного класса <tex>\Sigma_i \; \exists R_{L_f}^i \colon \langle x, y_1 \rangle \in L_f \Leftrightarrow \exists y_2 \forall y_3 \ldots Q y_{i+1} R_{L_f}^i(\langle x, y_1 \rangle, y_2 \ldots y_{i+1})</tex>. Тогда <tex>x \in L \Leftrightarrow \exists \langle y_1, y_2 \rangle \forall y_3 \ldots Q y_{i+1} R_L^i(x, \langle y_1, y_2\rangle \ldots y_{i+1})</tex>. 
<tex>R_L^i(x, \langle y_1, y_2\rangle, y_3 \ldots, y_{i+1})</tex>
'''return''' <tex>R_{L_f}^i(\langle x, y_1\rangle, y_2, y_3 \ldots y_{i+1})</tex>
Значит, <tex>L \in \Sigma_i</tex>. 
Заметим, что при <tex>i = 0</tex> теорема, скорее всего, неверна. Так как если взять язык <tex>L \in \Sigma_1</tex> и выполнить все шаги доказательства, то на выходе получится язык из <tex>\Sigma_1</tex>, а не из <tex>\Sigma_0</tex>.
}}

== См. также ==
*[[Классы PH, Σ и Π]]

Теоремы о коллапсе полиномиальной иерархии

2012-05-10T16:26:15Z

Andrey.Eremeev: /* Теорема о коллапсе полиномиальной иерархии при совпадении \Sigma_i и \Sigma_{i+1} */

{{Лемма
|statement = Если <tex>\Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Pi_i = \Pi_{i+1}</tex>.
|proof = <tex>L \in \Pi_{i+1} \Leftrightarrow \overline{L} \in \Sigma_{i+1} \Leftrightarrow \overline{L} \in \Sigma_i \Leftrightarrow L \in \Pi_i</tex>.
}}

== Теорема о коллапсе полиномиальной иерархии при совпадении <tex>\Sigma_i</tex> и <tex>\Sigma_{i+1}</tex> ==
{{Теорема
|statement = Если существует <tex>i \colon \Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Sigma_i = PH</tex>.
|proof = Для доказательства теоремы достаточно показать, что если такое <tex>i</tex> существует, то <tex>\forall j > i</tex> верно, что <tex>\Sigma_i = \Sigma_j</tex>. 
Докажем по индукции. 
'''База'''. <tex>\Sigma_i = \Sigma_{i+1}</tex> из условия. 
'''Индукционный переход'''. Докажем, что если <tex>\Sigma_n = \Sigma_{n+1}</tex>, то <tex>\Sigma_{n+1} = \Sigma_{n+2}</tex>. 
Рассмотрим язык <tex>L \in \Sigma_{n+2}</tex>. <tex>L = \{x \colon \exists y_1 \forall y_2 \ldots Q y_{n+2} R_L^{n+2}(x, y_1 \ldots y_{n+2})\}</tex>. Обозначим <tex>\forall y_2 \ldots Q y_{n+2} R_L^{n+2}(x, y_1 \ldots y_{n+2}) = f(x, y_1)</tex>.
Тогда получим язык <tex>L_f = \{\langle x, y_1\rangle \colon f(x, y_1) = 1\}</tex>. 
Заметим, что <tex>L_f \in \Pi_{n+1}</tex> и из вышедоказанной леммы следует, что <tex>L_f \in \Pi_n</tex>. 
Из определения сложностного класса <tex>\Pi_n</tex> получаем, что <tex>\exists R_{L_f}^{n} \colon \langle x, y_1 \rangle \in L_f \Leftrightarrow \forall y_2 \exists y_3 \ldots Q y_{n+1} R_{L_f}^{n}(\langle x, y_1\rangle, y_2 \ldots y_{n+1})</tex>. Следовательно, <tex>x \in L \Leftrightarrow \exists y_1 \forall y_2 \ldots Q y_{n+1} R_L^{n+1}(x, y_1, y_2 \ldots y_{n+1})</tex>.
<tex>R_L^{n+1}(x, y_1, y_2 \ldots y_{n+1})</tex>
'''return''' <tex>R_{L_f}^n(\langle x, y_1\rangle, y_2 \ldots y_{n+1})</tex>
То есть язык <tex>L \in \Sigma_{n+1}</tex>.
}}

== Теорема о коллапсе полиномиальной иерархии при совпадении <tex>\Sigma_i</tex> и <tex>\Pi_i</tex> ==
{{Теорема
|statement = Если существует <tex>i > 0\colon \Sigma_i = \Pi_i</tex>, то <tex>\Sigma_i = PH</tex>.
|proof =
Для доказательства покажем, что <tex>\Sigma_i = \Sigma_{i+1}</tex>, и воспользуемся предыдущей теоремой.

Рассмотрим язык <tex>L \in \Sigma_{i+1}</tex>. <tex>L =\{x \colon \exists y_1 \forall y_2 \ldots Q y_{i+1} R_L^{i+1}(x, y_1 \ldots y_{i+1})\}</tex>. Обозначим <tex>\forall y_2 \exists y_3 \ldots Q y_{i+1} R_L^{i+1}(x, y_1 \ldots y_{i+1}) = f(x, y_1)</tex>. Получим язык <tex>L_f = \{ \langle x, y_1 \rangle \colon f(x, y_1) = 1\}</tex>. 
Тогда <tex>L_f \in \Pi_i</tex>, и из условия теоремы <tex>L_f \in \Sigma_i</tex>. 
По определению сложностного класса <tex>\Sigma_i \; \exists R_{L_f}^i \colon \langle x, y_1 \rangle \in L_f \Leftrightarrow \exists y_2 \forall y_3 \ldots Q y_{i+1} R_{L_f}^i(\langle x, y_1 \rangle, y_2 \ldots y_{i+1})</tex>. Тогда <tex>x \in L \Leftrightarrow \exists \langle y_1, y_2 \rangle \forall y_3 \ldots Q y_{i+1} R_L^i(x, \langle y_1, y_2\rangle \ldots y_{i+1})</tex>. 
<tex>R_L^i(x, \langle y_1, y_2\rangle, y_3, \ldots, y_{i+1})</tex>
'''return''' <tex>R_{L_f}^i(\langle x, y_1\rangle, y_2, y_3, \ldots y_{i+1})</tex>
Значит, <tex>L \in \Sigma_i</tex>. 
Заметим, что при <tex>i = 0</tex> теорема, скорее всего, неверна. Так как если взять язык <tex>L \in \Sigma_1</tex> и выполнить все шаги доказательства, то на выходе получится язык из <tex>\Sigma_1</tex>, а не из <tex>\Sigma_0</tex>.
}}

== См. также ==
*[[Классы PH, Σ и Π]]

Теоремы о коллапсе полиномиальной иерархии

2012-05-10T16:19:34Z

Andrey.Eremeev: /* Теорема о коллапсе полиномиальной иерархии при совпадении \Sigma_i и \Sigma_{i+1} */

{{Лемма
|statement = Если <tex>\Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Pi_i = \Pi_{i+1}</tex>.
|proof = <tex>L \in \Pi_{i+1} \Leftrightarrow \overline{L} \in \Sigma_{i+1} \Leftrightarrow \overline{L} \in \Sigma_i \Leftrightarrow L \in \Pi_i</tex>.
}}

== Теорема о коллапсе полиномиальной иерархии при совпадении <tex>\Sigma_i</tex> и <tex>\Sigma_{i+1}</tex> ==
{{Теорема
|statement = Если существует <tex>i \colon \Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Sigma_i = PH</tex>.
|proof = Для доказательства теоремы достаточно показать, что если такое <tex>i</tex> существует, то <tex>\forall j > i</tex> верно, что <tex>\Sigma_i = \Sigma_j</tex>. 
Докажем по индукции. 
'''База'''. <tex>\Sigma_i = \Sigma_{i+1}</tex> из условия. 
'''Индукционный переход'''. Докажем, что если <tex>\Sigma_n = \Sigma_{n+1}</tex>, то <tex>\Sigma_{n+1} = \Sigma_{n+2}</tex>. 
Рассмотрим язык <tex>L \in \Sigma_{n+2}</tex>. <tex>L = \{x \colon \exists y_1 \forall y_2 \ldots Q y_{n+2} R_L^{n+2}(x, y_1 \ldots y_{n+2})\}</tex>. Обозначим <tex>\forall y_2 \ldots Q y_{n+2} R_L^{n+2}(x, y_1 \ldots y_{n+2}) = f(x, y_1)</tex>.
Тогда получим язык <tex>L_f = \{\langle x, y_1\rangle \colon f(x, y_1) = 1\}</tex>. 
Заметим, что <tex>L_f \in \Pi_{n+1}</tex> и из вышедоказанной леммы следует, что <tex>L_f \in \Pi_n</tex>. 
Из определения сложностного класса <tex>\Pi_n</tex> получаем, что <tex>\exists R_{L_f}^{n} \colon \langle x, y_1 \rangle \in L_f \Leftrightarrow \forall y_2 \exists y_3 \ldots Q y_{n+1} R_{L_f}^{n}(\langle x, y_1\rangle, y_2 \ldots y_{n+1})</tex>. Следовательно, <tex>x \in L \Leftrightarrow \exists y_1 \forall y_2 \ldots Q y_{n+1} R_{L_f}^{n}(\langle x, y_1\rangle, y_2 \ldots y_{n+1})</tex>. То есть язык <tex>L \in \Sigma_{n+1}</tex>.
}}

== Теорема о коллапсе полиномиальной иерархии при совпадении <tex>\Sigma_i</tex> и <tex>\Pi_i</tex> ==
{{Теорема
|statement = Если существует <tex>i > 0\colon \Sigma_i = \Pi_i</tex>, то <tex>\Sigma_i = PH</tex>.
|proof =
Для доказательства покажем, что <tex>\Sigma_i = \Sigma_{i+1}</tex>, и воспользуемся предыдущей теоремой.

Рассмотрим язык <tex>L \in \Sigma_{i+1}</tex>. <tex>L =\{x \colon \exists y_1 \forall y_2 \ldots Q y_{i+1} R_L^{i+1}(x, y_1 \ldots y_{i+1})\}</tex>. Обозначим <tex>\forall y_2 \exists y_3 \ldots Q y_{i+1} R_L^{i+1}(x, y_1 \ldots y_{i+1}) = f(x, y_1)</tex>. Получим язык <tex>L_f = \{ \langle x, y_1 \rangle \colon f(x, y_1) = 1\}</tex>. 
Тогда <tex>L_f \in \Pi_i</tex>, и из условия теоремы <tex>L_f \in \Sigma_i</tex>. 
По определению сложностного класса <tex>\Sigma_i \; \exists R_{L_f}^i \colon \langle x, y_1 \rangle \in L_f \Leftrightarrow \exists y_2 \forall y_3 \ldots Q y_{i+1} R_{L_f}^i(\langle x, y_1 \rangle, y_2 \ldots y_{i+1})</tex>. Тогда <tex>x \in L \Leftrightarrow \exists \langle y_1, y_2 \rangle \forall y_3 \ldots Q y_{i+1} R_L^i(x, \langle y_1, y_2\rangle \ldots y_{i+1})</tex>. 
<tex>R_L^i(x, \langle y_1, y_2\rangle, y_3, \ldots, y_{i+1})</tex>
'''return''' <tex>R_{L_f}^i(\langle x, y_1\rangle, y_2, y_3, \ldots y_{i+1})</tex>
Значит, <tex>L \in \Sigma_i</tex>. 
Заметим, что при <tex>i = 0</tex> теорема, скорее всего, неверна. Так как если взять язык <tex>L \in \Sigma_1</tex> и выполнить все шаги доказательства, то на выходе получится язык из <tex>\Sigma_1</tex>, а не из <tex>\Sigma_0</tex>.
}}

== См. также ==
*[[Классы PH, Σ и Π]]