Изменения

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

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

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

|statement= Пусть <tex>m</tex> — ВМТ. Тогда <tex>\forall x, \forall A</tex> — предикат от ВМТ<tex>m</tex>: <tex>R = \{r | A(m(x, r))\} \in \Sigma</tex>, т.е. <tex>R</tex> измеримо.

<tex>R_i \in \Sigma</tex>, <tex>\operatorname{P}(R_i) = \frac{1}{2^i} \cdot |\{s : |s| = i, s</tex> — префикс <tex>r \in R_i\}|</tex>, <tex>R_i</tex> дизъюнктны.

1) # <tex>\operatorname{P}(p(x) \ne [x \in L]) = 0</tex>;<br>2) # <tex>\operatorname{E}([\operatorname{T}(p(x))) ] = poly(|x|)</tex>.<br>

1) # <tex>x \notin L \Rightarrow \operatorname{P}(p(x) = 0) = 1</tex>;<br>2) # <tex>x \in L \Rightarrow \operatorname{P}(p(x) = 1) \ge 1/2</tex>;<br>3) # <tex>\forall r \operatorname{T}(p(x)) \le poly(|x|).</tex>

Определим также <tex>\mathrm{coRPRP}</tex> можно рассматривать как дополнение к вероятностный аналог класса <tex>\mathrm{RPNP}</tex>, предполагая, что вероятность угадать сертификат в случае его существования не менее <tex>1/2</tex>.

{{Определение|definition =<tex>\mathrm{RPcoRP}</tex> можно рассматривать как вероятностный аналог класса <tex>= \{L | \overline L \in \mathrm{NPRP}\}</tex>, предполагая, что вероятность угадать сертификат в случае его существования не менее <tex>1/2</tex>.}}

1) # <tex>\operatorname{P}(p(x) = [x \in L]) \ge 2/3</tex>;<br>2) # <tex>\forall r \operatorname{T}(p(x)) \le poly(|x|)</tex>.

Аналогично сделанному выше замечанию, константу <tex>2/3</tex> можно заменить на любое число из промежутка <tex>(1/2, 1)</tex>. Замена константы на <tex>1/2</tex> сделало бы данный класс равным <tex>\Sigma^*</tex>(программа, возвращающая результат функции ''random''(), подошла бы для любого языка).

1) # <tex>\operatorname{P}(p(x) = [x \in L]) > 1/2</tex>;<br>2) # <tex>\forall r \operatorname{T}(p(x)) \le poly(|x|)</tex>.

Утверждение <tex>\mathrm{P} \subset \mathrm{ZPP}</tex> является очевидным, так как программы, разрешающие удовлетворяющие ограничениям <tex>\mathrm{P}</tex>, также удовлетворяют ограничениям класса <tex>\mathrm{ZPP}</tex>.

1) # <tex>p(x) \in \{0, 1, ?\}</tex>; 2) # <tex>p(x) \ne \enskip? \Rightarrow p(x) = [x \in L]</tex>; 3) # <tex>\operatorname{P}(p(x) = \enskip?) \le 1/2</tex>; 4) # <tex>\forall r \operatorname{T}(p(x)) \le poly(|x|).</tex>

1. Сначала докажем, что <tex>\mathrm{ZPP} = \mathrm{ZPP}_1</tex>.

Подставляем Подставим <tex>k = 2</tex>. Тогда, если запустить программу <tex>p</tex> для <tex>\mathrm{ZPP}</tex> с ограничением по времени <tex>2E[X]</tex>, она не успеет завершиться с вероятностью, не превышающей <tex>1/2</tex>. В этом случае программа Опишем программу <tex>q</tex> для <tex>\mathrm{ZPP}_1</tex> вернет . Она будет возвращать <tex>?</tex>, если <tex>p</tex> не успеет завершиться, а иначе — результат работы программы <tex>p</tex>. Заметим, что <tex>q</tex> работает полиномиальное время, так как <tex>E[X]</tex> ограничено некоторым полиномом по определению класса <tex>\mathrm{ZPP}</tex>.

2) <tex>\mathrm{ZPP_1} \subset \mathrm{ZPP}</tex>. Будем запускать программу <tex>p </tex> для <tex>\mathrm{ZPP_1}</tex>, пока не получим ответ, отличный от <tex>?</tex>. Математическое ожидание количества запусков <tex>p</tex> не превышает <tex>\sum\limits_{k = 0}^\infty \frac{k}{2^k} = 2</tex>. Значит, новая программа будет в среднем работать за полиномиальное время, что и требуется для класса <tex>\mathrm{ZPP}</tex>.

2. Теперь покажем, что <tex>\mathrm{ZPP}_1 = \mathrm{RP} \cap \mathrm{coRP}</tex>.

Пусть программа <tex>pp_1</tex> ошибается на словах из языка с вероятностью не более удовлетворяет ограничениям <tex>1/2</tex>, <tex>qRP</tex> и ошибается на словах не из языка с аналогичной вероятностью. Вычислим значения <tex>p(x)L</tex> и с вероятностью не более <tex>q(x)<1/tex>. Вернем <tex>02</tex>, если а программа <tex>p(x) = 0p_2</tex>. Вернем удовлетворяет ограничениям <tex>1coRP</tex>, если и ошибается на словах не из языка <tex>q(x) = 1L</tex>с аналогичной вероятностью. В противном случае вернем Построим программу <tex>?q</tex>. Вероятность вывести для <tex>?\mathrm{ZPP}_1</tex> есть <tex>\operatorname{P}: q(x): '''if''' p(x) = 1, 0: '''return''' 0 '''if'' q(x) = 0) \le 1/2</tex>.: '''return''' 1 '''return''' ?