Вероятностные вычисления. Вероятностная машина Тьюринга
Вероятностные вычисления — один из подходов в теории вычислительной сложности, в котором программы получают доступ к случайным битам. Мы рассмотрим классы сложности, для которых разрешающие программы могут делать односторонние, двусторонние ошибки или работать за полиномиальное время лишь в среднем случае.
Основные определения
Определение: |
Вероятностная лента — бесконечная последовательность битов. Распределение битов на ленте подчиняется некоторому вероятностному закону (обычно считают, что вероятность нахождения | или в каждой позиции равна ).
Определение: |
Вероятностной машиной Тьюринга будем называть машину Тьюринга, имеющее доступ к вероятностной ленте. |
При интерпретации вероятностной машины Тьюринга как программы, обращение к очередному биту можно трактовать как вызов специальной функции 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(). Таким образом, мы построили программу , удовлетворяющую ограничениям класса .
|