|
|
| (не показано 45 промежуточных версий 6 участников) |
| Строка 1: |
Строка 1: |
| − | {{В разработке}}
| |
| | [[Категория: Теория сложности]] | | [[Категория: Теория сложности]] |
| − | Вероятностные вычисления — один из подходов в теории вычислительной сложности, в котором программы получают доступ к случайным битам. Мы рассмотрим классы сложности, для которых разрешающие программы могут делать односторонние, двусторонние ошибки или работать за полиномиальное время лишь в среднем случае. | + | '''Вероятностные вычисления''' — один из подходов в теории вычислительной сложности, в котором программы получают доступ, говоря неформально, к генератору случайных чисел. Мы рассмотрим классы сложности, для которых программы могут работать за полиномиальное время и делать односторонние, двусторонние ошибки или работать за полиномиальное время лишь в среднем случае. |
| | | | |
| − | == Основные определения ==
| |
| | {{Определение | | {{Определение |
| | |definition = | | |definition = |
| − | '''Вероятностная лента''' — бесконечная последовательность битов. Распределение битов на ленте подчиняется некоторому вероятностному закону (обычно считают, что вероятность нахождения <tex>0</tex> или <tex>1</tex> в каждой позиции равна <tex>1/2</tex>). | + | '''Вероятностная лента''' — бесконечная в одну сторону последовательность битов, распределение которых подчиняется некоторому вероятностному закону (обычно считают, что биты в различных позициях независимы и вероятность нахождения <tex>0</tex> или <tex>1</tex> в каждой позиции равна <tex>1/2</tex>). |
| | }} | | }} |
| | {{Определение | | {{Определение |
| | |definition = | | |definition = |
| − | '''Вероятностной машиной Тьюринга''' будем называть машину Тьюринга, имеющее доступ к вероятностной ленте. | + | '''Вероятностная машина Тьюринга''' (ВМТ) — детерминированная машина Тьюринга, имеющая вероятностную ленту. Переходы в ВМТ могут осуществляться с учетом информации, считанной с вероятностной ленты. |
| | }} | | }} |
| | | | |
| − | При интерпретации вероятностной машины Тьюринга как программы, обращение к очередному биту можно трактовать как вызов специальной функции ''random''(). При этом также будем предполагать, что вероятностная лента является неявным аргументом для программы, т.е. <tex>p(x) = p(x, r)</tex>, где <tex>r</tex> — вероятностная лента.
| + | Используя тезис Черча-Тьюринга, ВМТ можно сопоставить программы, имеющие доступ к случайным битам. Обращение к очередному биту можно трактовать как вызов специальной функции ''random''(). При этом также будем предполагать, что вероятностная лента является неявным аргументом программы или ВМТ, т.е. <tex>p(x) = p(x, r)</tex>, где <tex>r</tex> — вероятностная лента. |
| − | <br>
| |
| − | В дальнейшем все вероятностные соображения будут относиться к пространству вероятностных лент <tex>r</tex>, вход же программы <tex>x</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> порождена событиями, зависящими лишь от конечного числа бит вероятностной ленты (то есть существующими в дискретных вероятностных пространствах). Покажем, что любой предикат от ВМТ является событием. |
| − | | |
| − | | |
| − | == Вероятностные сложностные классы ==
| |
| − | {{Определение
| |
| − | |definition =
| |
| − | <tex>\mathrm{ZPP}</tex> (от ''zero-error probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:
| |
| − | 1) <tex>\operatorname{P}(p(x) \ne [x \in L]) = 0</tex>;<br>
| |
| − | 2) <tex>\operatorname{E}(\operatorname{T}(p(x))) = poly(|x|)</tex>.<br>
| |
| − | }}
| |
| − | | |
| − | {{Определение
| |
| − | |definition =
| |
| − | <tex>\mathrm{RP}</tex> (от ''randomized polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>: | |
| − | 1) <tex>x \notin L \Rightarrow p(x) = 0</tex>;<br>
| |
| − | 2) <tex>x \in L \Rightarrow \operatorname{P}(p(x) = 1) \ge 1/2</tex>;<br>
| |
| − | 3) <tex>\forall r \operatorname{T}(p(x)) \le poly(|x|).</tex>
| |
| − | }}
| |
| − | Заметим, что константа <tex>1/2</tex> в пункте 2 определения <tex>\mathrm{RP}</tex> может быть заменена на любую другую из промежутка <tex>(0, 1)</tex>, поскольку требуемой вероятности можно добиться множественным запуском программы.
| |
| − | Определим также <tex>\mathrm{coRP}</tex> как дополнение к <tex>\mathrm{RP}</tex>.
| |
| − | | |
| − | <tex>\mathrm{RP}</tex> можно рассматривать как вероятностный аналог класса <tex>\mathrm{NP}</tex>, предполагая, что вероятность угадать сертификат в случае его существования не менее <tex>1/2</tex>.
| |
| − | | |
| − | {{Определение
| |
| − | |definition =
| |
| − | <tex>\mathrm{BPP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>: | |
| − | 1) <tex>\operatorname{P}(p(x) = [x \in L]) \ge 2/3</tex>;<br>
| |
| − | 2) <tex>\operatorname{T}(p(x)) \le poly(|x|)</tex>.
| |
| − | }}
| |
| − | Аналогично сделанному выше замечанию, константу <tex>2/3</tex> можно заменить на любое число из промежутка <tex>(1/2, 1)</tex>. Замена константы на <tex>1/2</tex> сделало бы данный класс равным <tex>\Sigma^*</tex>.
| |
| − | | |
| − | {{Определение
| |
| − | |definition =
| |
| − | <tex>\mathrm{PP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:
| |
| − | 1) <tex>\operatorname{P}(p(x) = [x \in L]) > 1/2</tex>;<br>
| |
| − | 2) <tex>\operatorname{T}(p(x)) \le poly(|x|)</tex>.
| |
| − | }}
| |
| − | | |
| − | == Соотношение вероятностных классов ==
| |
| | {{Теорема | | {{Теорема |
| − | |statement = | + | |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> измеримо. |
| − | 1. <tex>\mathrm{P} \subset \mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>
| + | |proof= |
| − | 2. <tex>\mathrm{RP} \subset \mathrm{NP} \subset \mathrm{PP} \subset \mathrm{PS}</tex>
| + | <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> следует, что они дизъюнктны. |
| − | 3. <tex>\mathrm{RP} \subset \mathrm{BPP}</tex>
| |
| − | |proof =
| |
| − | 1. Утверждение <tex>\mathrm{P} \subset \mathrm{ZPP}</tex> является очевидным, так как программы, разрешающие <tex>\mathrm{P}</tex>, удовлетворяют ограничениям класса <tex>\mathrm{ZPP}</tex>.
| |
| − | <br>
| |
| − | Покажем, что <tex>\mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>.
| |
| − | ...
| |
| − | <br>
| |
| − | 2. Покажем, что <tex>\mathrm{RP} \subset \mathrm{NP}</tex>. Если в разрешающей программе для <tex>L \in \mathrm{RP}</tex> заменить все вызовы ''random''() на недетерминированный выбор, то получим программу с ограничениями <tex>\mathrm{NP}</tex>, разрешающую <tex>L</tex>.
| |
| − | <br>
| |
| − | Покажем, что <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> оказалось больше.
| |
| − | <br>
| |
| − | Теперь докажем, что <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> будет выглядеть следующим образом:
| |
| − | q(x):
| |
| − | c <- случайный сертификат (полиномиальной длины)
| |
| − | '''return''' V(x, c) ? 1 : infair_coin()
| |
| − | Необходимо удовлетворить условию <tex>\operatorname{P}(p(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}(p(x) = 1) = p_0 + (1 - p_0) (1/2 - \varepsilon)</tex>, где <tex>p_0</tex> — вероятность угадать правильный сертификат. Заметим, что поскольку все сертификаты имеют полиномиальную длину и существует хотя бы один правильный сертификат, <tex>p_0</tex> не более чем экспоненциально мала. Найдем <tex>\varepsilon</tex> из неравенства <tex>\operatorname{P}(p(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 < p_0 (1 - p_0) / 2</tex>. | |
| − | | |
| − | Достаточно взять <tex>\varepsilon < p_0 / 4</tex>. Из сделанного выше замечания следует, что работу функции ''infair_coin''() можно смоделировать с помощью полиномиального количества вызовов ''random''(). Таким образом, мы построили программу <tex>q</tex>, удовлетворяющую ограничениям класса <tex>\mathrm{PP}</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>. |
| | | | |
| − | 3. ...
| + | <tex>R \in \Sigma</tex> как счетное объединение событий, при этом из их дизъюнктности следует, что <tex>\operatorname{P}(R) = \sum\limits_{i = 0}^{\infty} \operatorname{P}(R_i)</tex>. |
| | }} | | }} |
| | | | |
| | == См. также == | | == См. также == |
| − | * [[Теоремы о BPP, BPPweak и BPPstrong]] | + | * [[Классы RP и coRP]] |
| − | * [[Уменьшение ошибки в классе RP]] | + | * [[Класс ZPP]] |
| − | * [[Теорема Лаутемана]] | + | * [[Класс BPP]] |
| | | | |
| | == Литература == | | == Литература == |
| − | * [http://www.cs.princeton.edu/theory/complexity/book.pdf Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach] | + | * [http://www.cs.princeton.edu/theory/complexity/ Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach] |
Вероятностные вычисления — один из подходов в теории вычислительной сложности, в котором программы получают доступ, говоря неформально, к генератору случайных чисел. Мы рассмотрим классы сложности, для которых программы могут работать за полиномиальное время и делать односторонние, двусторонние ошибки или работать за полиномиальное время лишь в среднем случае.
| Определение: |
| Вероятностная лента — бесконечная в одну сторону последовательность битов, распределение которых подчиняется некоторому вероятностному закону (обычно считают, что биты в различных позициях независимы и вероятность нахождения [math]0[/math] или [math]1[/math] в каждой позиции равна [math]1/2[/math]). |
| Определение: |
| Вероятностная машина Тьюринга (ВМТ) — детерминированная машина Тьюринга, имеющая вероятностную ленту. Переходы в ВМТ могут осуществляться с учетом информации, считанной с вероятностной ленты. |
Используя тезис Черча-Тьюринга, ВМТ можно сопоставить программы, имеющие доступ к случайным битам. Обращение к очередному биту можно трактовать как вызов специальной функции random(). При этом также будем предполагать, что вероятностная лента является неявным аргументом программы или ВМТ, т.е. [math]p(x) = p(x, r)[/math], где [math]r[/math] — вероятностная лента.
Введем вероятностное пространство [math](\Omega, \Sigma, \operatorname{P})[/math], где пространство элементарных исходов [math]\Omega[/math] — множество всех вероятностных лент, [math]\Sigma[/math] — сигма-алгебра подмножеств [math]\Omega[/math], [math]\operatorname{P}[/math] — вероятностная мера, заданная на [math]\Sigma[/math]. Будем считать, что [math]\Sigma[/math] порождена событиями, зависящими лишь от конечного числа бит вероятностной ленты (то есть существующими в дискретных вероятностных пространствах). Покажем, что любой предикат от ВМТ является событием.
| Теорема: |
Пусть [math]m[/math] — ВМТ. Тогда для любых [math]x[/math] и [math]A[/math] — предиката от [math]m[/math] выполняется [math]R = \{r \bigm| A(m(x, r))\} \in \Sigma[/math], т.е. [math]R[/math] измеримо. |
| Доказательство: |
| [math]\triangleright[/math] |
|
[math]R = \bigcup\limits_{i = 0}^\infty R_i[/math], где [math]R_i = \{r \bigm| A(m(x, r)), m[/math] прочитала ровно [math]i[/math] первых символов с [math]r\}[/math]. Это верно, поскольку мы рассматриваем только завершающиеся ВМТ. Кроме того, из определения [math]R_i[/math] следует, что они дизъюнктны.
[math]R_i \in \Sigma[/math] как зависящие от [math]i[/math] первых битов вероятностной ленты, [math]\operatorname{P}(R_i) = \frac{1}{2^i} \cdot |\{s \bigm| |s| = i, s[/math] — префикс [math]r \in R_i\}|[/math].
[math]R \in \Sigma[/math] как счетное объединение событий, при этом из их дизъюнктности следует, что [math]\operatorname{P}(R) = \sum\limits_{i = 0}^{\infty} \operatorname{P}(R_i)[/math]. |
| [math]\triangleleft[/math] |
См. также
Литература
