Вероятностные вычисления. Вероятностная машина Тьюринга
Вероятностные вычисления — один из подходов в теории вычислительной сложности, в котором программы получают доступ, говоря неформально, к генератору случайных чисел. Мы рассмотрим классы сложности, для которых программы могут работать за полиномиальное время и делать односторонние, двусторонние ошибки или работать за полиномиальное время лишь в среднем случае.
Основные определения
| Определение: |
| Вероятностная лента — бесконечная в одну сторону последовательность битов, распределение которых подчиняется некоторому вероятностному закону (обычно считают, что биты в различных позициях независимы и вероятность нахождения или в каждой позиции равна ). |
| Определение: |
| Вероятностная машина Тьюринга (ВМТ) — детерминированная машина Тьюринга, имеющая вероятностную ленту. Переходы в ВМТ могут осуществляться с учетом информации, считанной с вероятностной ленты. |
Используя тезис Черча-Тьюринга, ВМТ можно сопоставить программы, имеющие доступ к случайным битам. Обращение к очередному биту можно трактовать как вызов специальной функции random(). При этом также будем предполагать, что вероятностная лента является неявным аргументом программы или ВМТ, т.е. , где — вероятностная лента.
Введем вероятностное пространство , где пространство элементарных исходов — множество всех вероятностных лент, — сигма-алгебра подмножеств , — вероятностная мера, заданная на . Будем считать, что порождена событиями, зависящими лишь от конечного числа бит вероятностной ленты (то есть существующими в дискретных вероятностных пространствах). Покажем, что любой предикат от ВМТ является событием.
| Теорема: |
Пусть — ВМТ. Тогда для любых и — предиката от выполняется , т.е. измеримо. |
| Доказательство: |
|
, где прочитала ровно первых символов с . Это верно, поскольку мы рассматриваем только завершающиеся ВМТ. Кроме того, из определения следует, что они дизъюнктны. как зависящие от первых битов вероятностной ленты, — префикс . как счетное объединение событий, при этом из их дизъюнктности следует, что . |
Вероятностные сложностные классы
| Определение: |
(от zero-error probabilistic polynomial) — множество языков , для которых :
|
— сложностный класс, такой что программы, удовлетворяющие его ограничениям, не могут делать ошибок, но работают за полиномиальное время только в среднем случае.
Напомним, что математическое ожидание является усреднением по вероятностным лентам, а не по входу .
| Определение: |
(от randomized polynomial) — множество языков , для которых :
|
— сложностный класс, допускающий ошибки программ на словах из . Заметим, что константа в пункте 2 определения может быть заменена на любую другую из промежутка , поскольку требуемой вероятности можно добиться множественным запуском программы.
можно рассматривать как вероятностный аналог класса , предполагая, что вероятность угадать сертификат в случае его существования не менее .
| Определение: |
| . |
Класс допускает ошибки программ на словах, не принадлежащих .
| Определение: |
(от bounded probabilistic polynomial) — множество языков , для которых :
|
— сложностный класс, допускающий двусторонние ошибки. Аналогично сделанному выше замечанию, константу можно заменить на любое число из промежутка . Замена константы на сделало бы данный класс равным (программа, возвращающая результат функции random(), подошла бы для любого языка).
| Определение: |
(от probabilistic polynomial) — множество языков , для которых :
|
также допускает двусторонние ошибки, но является более широким по сравнению с .
Соотношение вероятностных классов
| Теорема: | ||
. | ||
| Доказательство: | ||
|
Утверждение является очевидным, так как программы, удовлетворяющие ограничениям , также удовлетворяют ограничениям класса . Покажем, что . Для этого определим вспомогательный класс .
1. Сначала докажем, что . 1) . Пусть — случайная величина, равная времени работы программы для , . Запишем неравенство Маркова: . Подставим . Тогда, если запустить программу для с ограничением по времени , она не успеет завершиться с вероятностью, не превышающей . Опишем программу для . Она будет возвращать , если не успеет завершиться, а иначе — результат работы программы . Заметим, что работает полиномиальное время, так как ограничено некоторым полиномом по определению класса . 2) . Будем запускать программу для , пока не получим ответ, отличный от . Математическое ожидание количества запусков не превышает . Значит, новая программа будет в среднем работать за полиномиальное время, что и требуется для класса . 2. Теперь покажем, что . 1) . Достаточно вместо возвращать . 2) . Достаточно вместо возвращать . 3) . Пусть программа удовлетворяет ограничениям и ошибается на словах из языка с вероятностью не более , а программа удовлетворяет ограничениям и ошибается на словах не из языка с аналогичной вероятностью. Построим программу для : q(x)
if p(x) = 0
return 0
if q(x) = 1
return 1
return ?
Вероятность вывести есть . | ||
| Теорема: |
. |
| Доказательство: |
|
1. . Если в программе для заменить все вызовы random() на недетерминированный выбор, то получим программу для с ограничениями . 2. . Приведем программу с ограничениями класса , которая разрешает . Пусть функция infair_coin() моделирует нечестную монету, а именно возвращает единицу с вероятностью , где мы определим позже, и ноль с вероятностью . Пусть также — верификатор сертификатов для . Тогда будет выглядеть следующим образом: q(x)
c <- случайный сертификат (полиномиальной длины)
if V(x, c)
return 1
return infair_coin()
Необходимо удовлетворить условию . Пусть . В этом случае вернет и результат работы программы будет зависеть от нечестной монеты. Она вернет с вероятностью . Пусть . Тогда по формуле полной вероятности , где — вероятность угадать правильный сертификат. Заметим, что поскольку длина всех сертификатов ограничена некоторым полиномом и существует хотя бы один правильный сертификат, . Найдем из неравенства : ; ; . Достаточно взять . Из сделанного выше замечания следует, что работу функции infair_coin() можно смоделировать с помощью не более чем вызовов random(). Таким образом, мы построили программу , удовлетворяющую ограничениям класса . 3. . Пусть — программа для языка . Она используют не более чем полиномиальное количество вероятностных бит, так как сама работает за полиномиальное время. Тогда программа для будет перебирать все участки вероятностных лент нужной полиномиальной длины и запускать на них . Ответом будет или в зависимости от того, каких ответов оказалось больше. |
| Теорема: |
. |
| Доказательство: |
|
Пусть — программа для . Программу для определим следующим образом: q(x) u <- p(x) v <- p(x) return u or v Пусть . В этом случае вероятность ошибки равна . Пусть . Тогда с вероятностью будет верно и вернет правильный ответ. Аналогично доказывается, что . |
