70
правок
Изменения
м
Нет описания правки
'''return''' 1
'''return''' infair_coin()
Необходимо удовлетворить условию <tex>\operatorname{P}(pq(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}(pq(x) = 1) = p_0 + (1 - p_0) (1/2 - \varepsilon)</tex>, где <tex>p_0</tex> — вероятность угадать правильный сертификат. Заметим, что поскольку длина всех сертификатов ограничена некоторым полиномом <tex>s(n), n = |x|</tex> и существует хотя бы один правильный сертификат, <tex>p_0 \ge 2^{-s(n)}</tex>. Найдем <tex>\varepsilon</tex> из неравенства <tex>\operatorname{P}(pq(x) = 1) > 1/2</tex>:
<tex>p_0 + 1/2 - \varepsilon - p_0 / 2 + p_0 \varepsilon > 1/2</tex>;
