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