Изменения

<tex>\mathrm{ZPP}</tex> (от ''zero-error probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:

# <tex>\operatorname{P}(p(x) \ne [x \in L]) = 0</tex>;<br>

}}

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

# <tex>x \notin L \Rightarrow \operatorname{P}(p(x) = 0) = 1</tex>;<br>

# <tex>x \in L \Rightarrow \operatorname{P}(p(x) = 1) \ge 1/2</tex>;<br>

}}

<tex>\mathrm{RP}</tex> — сложностный класс, допускающий ошибки программ на словах из <tex>L</tex>.

<tex>\mathrm{BPP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:

# <tex>\operatorname{P}(p(x) = [x \in L]) \ge 2/3</tex>;

}}

<tex>\mathrm{BPP}</tex> — сложностный класс, допускающий двусторонние ошибки.

<tex>\mathrm{PP}</tex> (от ''probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:

# <tex>\operatorname{P}(p(x) = [x \in L]) > 1/2</tex>;

}}

<tex>\mathrm{PP}</tex> также допускает двусторонние ошибки, но является более широким по сравнению с <tex>\mathrm{BPP}</tex>.

# <tex>p(x) \ne \enskip? \Rightarrow p(x) = [x \in L]</tex>;

# <tex>\operatorname{P}(p(x) = \enskip?) \le 1/2</tex>;

}}

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

3) <tex>\mathrm{ZPP}_1 \supset \mathrm{RP} \cap \mathrm{coRP}</tex>.

Пусть программа <tex>p_1</tex> удовлетворяет ограничениям <tex>\mathrm{RP}</tex> и ошибается на словах из языка <tex>L</tex> с вероятностью не более <tex>1/2</tex>, а программа <tex>p_2</tex> удовлетворяет ограничениям <tex>\mathrm{coRP}</tex> и ошибается на словах не из языка <tex>L</tex> с аналогичной вероятностью. Построим программу <tex>q</tex> для <tex>\mathrm{ZPP}_1</tex>:

'''if''' <tex>p_2</tex>(x) = 0

'''return''' 0

2. <tex>\mathrm{NP} \subset \mathrm{PP}</tex>. Приведем программу <tex>q</tex> с ограничениями класса <tex>\mathrm{PP}</tex>, которая разрешает <tex>L \in \mathrm{NP}</tex>. Пусть функция ''infair_coin''() моделирует нечестную монету, а именно возвращает единицу с вероятностью <tex>1/2 - \varepsilon</tex>, где <tex>\varepsilon</tex> мы определим позже, и ноль с вероятностью <tex>1/2 + \varepsilon</tex>. Пусть также <tex>V</tex> — верификатор сертификатов для <tex>L</tex>. Тогда <tex>q</tex> будет выглядеть следующим образом:

'''return''' 1

'''return''' infair_coin()

<tex>\varepsilon < \frac{p_0}{2 (1 - p_0)}</tex>.

3. <tex>\mathrm{PP} \subset \mathrm{PS}</tex>. Пусть <tex>p</tex> — программа для языка <tex>L \in \mathrm{PP}</tex>. Она используют не более чем полиномиальное количество вероятностных бит, так как сама работает за полиномиальное время. Тогда программа для <tex>\mathrm{PS}</tex> будет перебирать все участки вероятностных лент нужной полиномиальной длины и запускать на них <tex>p</tex>. Ответом будет <tex>0</tex> или <tex>1</tex> в зависимости от того, каких ответов <tex>p</tex> оказалось больше.

|proof =

Пусть <tex>p</tex> — программа для <tex>L \in \mathrm{RP}</tex>. Программу <tex>q</tex> для <tex>\mathrm{BPP}</tex> определим следующим образом:

'''return''' u '''or''' v

Пусть <tex>x \in L</tex>. В этом случае вероятность ошибки равна <tex>\operatorname{P}(u = 0, v = 0) = \operatorname{P}(u = 0) \cdot \operatorname{P}(v = 0) \le 1/4</tex>.