Вероятностные вычисления. Вероятностная машина Тьюринга

Материал из Викиконспекты
Версия от 23:20, 4 июня 2012; Igor buzhinsky (обсуждение | вклад) (Вероятностные классы сложности: Убрано уже перемещенное определение)
Перейти к: навигация, поиск

Вероятностные вычисления — один из подходов в теории вычислительной сложности, в котором программы получают доступ, говоря неформально, к генератору случайных чисел. Мы рассмотрим классы сложности, для которых программы могут работать за полиномиальное время и делать односторонние, двусторонние ошибки или работать за полиномиальное время лишь в среднем случае.

Основные определения

Определение:
Вероятностная лента — бесконечная в одну сторону последовательность битов, распределение которых подчиняется некоторому вероятностному закону (обычно считают, что биты в различных позициях независимы и вероятность нахождения 0 или 1 в каждой позиции равна 1/2).


Определение:
Вероятностная машина Тьюринга (ВМТ) — детерминированная машина Тьюринга, имеющая вероятностную ленту. Переходы в ВМТ могут осуществляться с учетом информации, считанной с вероятностной ленты.


Используя тезис Черча-Тьюринга, ВМТ можно сопоставить программы, имеющие доступ к случайным битам. Обращение к очередному биту можно трактовать как вызов специальной функции random(). При этом также будем предполагать, что вероятностная лента является неявным аргументом программы или ВМТ, т.е. p(x)=p(x,r), где r — вероятностная лента.

Введем вероятностное пространство (Ω,Σ,P), где пространство элементарных исходов Ω — множество всех вероятностных лент, Σ — сигма-алгебра подмножеств Ω, P — вероятностная мера, заданная на Σ. Будем считать, что Σ порождена событиями, зависящими лишь от конечного числа бит вероятностной ленты (то есть существующими в дискретных вероятностных пространствах). Покажем, что любой предикат от ВМТ является событием.

Теорема:
Пусть m — ВМТ. Тогда для любых x и A — предиката от m выполняется R={r|A(m(x,r))}Σ, т.е. R измеримо.
Доказательство:

R=i=0Ri, где Ri={r|A(m(x,r)),m прочитала ровно i первых символов с r}. Это верно, поскольку мы рассматриваем только завершающиеся ВМТ. Кроме того, из определения Ri следует, что они дизъюнктны.

RiΣ как зависящие от i первых битов вероятностной ленты, P(Ri)=12i|{s||s|=i,s — префикс rRi}|.

RΣ как счетное объединение событий, при этом из их дизъюнктности следует, что P(R)=i=0P(Ri).

Вероятностные классы сложности

Определение:
PP (от probabilistic polynomial) — множество языков L, для которых px:
  1. P(p(x)=[xL])>1/2;
  2. rT(p,x)poly(|x|).

PP также допускает двусторонние ошибки, но является более широким по сравнению с BPP.

Соотношение вероятностных классов

Теорема:
RPNPPPPS.
Доказательство:

1. RPNP. Если в программе для LRP заменить все вызовы random() на недетерминированный выбор, то получим программу для L с ограничениями NP.

2. NPPP. Приведем программу q с ограничениями класса PP, которая разрешает LNP. Пусть функция infair_coin() моделирует нечестную монету, а именно возвращает единицу с вероятностью 1/2ε, где ε мы определим позже, и ноль с вероятностью 1/2+ε. Пусть также V — верификатор сертификатов для L. Тогда q будет выглядеть следующим образом:

 q(x)
   c <- случайный сертификат
   if V(x, c)
     return 1
   return infair_coin()

Необходимо удовлетворить условию P(q(x)=[xL])>1/2.

Пусть xL. В этом случае V(x,c) вернет 0 и результат работы программы будет зависеть от нечестной монеты. Она вернет 0 с вероятностью 1/2+ε>1/2.

Пусть xL. Тогда по формуле полной вероятности P(q(x)=1)=p0+(1p0)(1/2ε), где p0 — вероятность угадать правильный сертификат. Заметим, что поскольку длина всех сертификатов ограничена некоторым полиномом s(n),n=|x| и существует хотя бы один правильный сертификат, p02s(n). Найдем ε из неравенства P(q(x)=1)>1/2:

p0+1/2εp0/2+p0ε>1/2;

p0/2+(p01)ε>0;

ε<p02(1p0).

Достаточно взять εp0/2. Из сделанного выше замечания следует, что работу функции infair_coin() можно смоделировать с помощью не более чем s(n)+1 вызовов random(). Также учтем, что длина сертификата и время работы V полиномиальны относительно |x|. Таким образом, мы построили программу q, удовлетворяющую ограничениям класса PP.

3. PPPS. Пусть p — программа для языка LPP. Она используют не более чем полиномиальное количество вероятностных бит, так как сама работает за полиномиальное время. Тогда программа для PS будет перебирать все участки вероятностных лент нужной полиномиальной длины и запускать на них p. Ответом будет 0 или 1 в зависимости от того, каких ответов p оказалось больше.

См. также

Литература