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