322
правки
Изменения
→Соотношение вероятностных классов
'''if''' p(x) = 0:
'''return''' 0
'''if''' q(x) = 1:
'''return''' 1
'''return''' ?
|statement = <tex>\mathrm{RP} \subset \mathrm{NP} \subset \mathrm{PP} \subset \mathrm{PS}</tex>.
|proof =
q(x):
c <- случайный сертификат (полиномиальной длины)
'''returnif''' V(x, c) ? : '''return''' 1 : '''return''' infair_coin()
Необходимо удовлетворить условию <tex>\operatorname{P}(p(x) = [x \in L]) > 1/2</tex>.
Пусть <tex>x \notin L</tex>. В этом случае <tex>V(x, c)</tex> вернет <tex>0</tex> и результат работы программы будет зависеть от нечестной монеты. Она вернет <tex>0</tex> с вероятностью <tex>1/2 + \varepsilon > 1/2</tex>.
Пусть <tex>x \in L</tex>. Тогда [[Формула полной вероятности|по формуле полной вероятности ]] <tex>\operatorname{P}(p(x) = 1) = p_0 + (1 - p_0) (1/2 - \varepsilon)</tex>, где <tex>p_0</tex> — вероятность угадать правильный сертификат. Заметим, что поскольку все сертификаты имеют полиномиальную длину и существует хотя бы один правильный сертификат, <tex>p_0</tex> не более чем экспоненциально мала. Найдем <tex>\varepsilon</tex> из неравенства <tex>\operatorname{P}(p(x) = 1) > 1/2</tex>: <tex>p_0 + 1/2 - \varepsilon - p_0 / 2 + p_0 \varepsilon > 1/2</tex>;
<tex>p_0 + 1/2 - \varepsilon - p_0 / 2 + p_0 \varepsilon > 1/2</tex>; <tex>p_0 / 2 + (p_0 - 1)\varepsilon > 0</tex>;<tex>\varepsilon < \frac{p_0}{2 (1 - p_0)}</tex>.
Достаточно взять <tex>\varepsilon < p_0 / 2</tex>. Из сделанного выше замечания следует, что работу функции ''infair_coin''() можно смоделировать с помощью полиномиального количества вызовов ''random''(1 - p_0) . Таким образом, мы построили программу <tex>q</ 2tex>, удовлетворяющую ограничениям класса <tex>\mathrm{PP}</tex>.
}}
{{Теорема
|statement =
|proof =
Пусть <tex>p</tex> — программа для <tex>L \in RP</tex>. Программу <tex>q</tex> для <tex>\mathrm{BPP}</tex> определим следующим образом:
Пусть <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>.
Пусть <tex>x \notin L</tex>. Тогда с вероятностью <tex>1</tex> будет верно <tex>u = 0, v = 0</tex> и <tex>q</tex> вернет правильный ответ.
Аналогично доказывается, что <tex>\mathrm{coRP} \subset \mathrm{BPP}</tex>.
