322
правки
Изменения
Нет описания правки
{{В разработке}}
[[Категория: Теория сложности]]
'''Вероятностные вычисления''' — один из подходов в теории вычислительной сложности, в котором программы получают доступ, говоря неформально, к генератору случайных чисел. Мы рассмотрим классы сложности, для которых программы могут работать за полиномиальное время и делать односторонние, двусторонние ошибки или работать за полиномиальное время лишь в среднем случае.
3) <tex>\mathrm{ZPP}_1 \supset \mathrm{RP} \cap \mathrm{coRP}</tex>.
Пусть программа <tex>p_1</tex> удовлетворяет ограничениям <tex>RP</tex> и ошибается на словах из языка <tex>L</tex> с вероятностью не более <tex>1/2</tex>, а программа <tex>p_2</tex> удовлетворяет ограничениям <tex>coRP</tex> и ошибается на словах не из языка <tex>L</tex> с аналогичной вероятностью. Построим программу <tex>q</tex> для <tex>\mathrm{ZPP}_1</tex>:
q(x): '''if''' p(x) = 0:
'''return''' 0
'''if''' q(x) = 1:
'''return''' 1
'''return''' ?
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> будет выглядеть следующим образом:
q(x):
c <- случайный сертификат (полиномиальной длины)
'''if''' V(x, c):
'''return''' 1
'''return''' infair_coin()
|proof =
Пусть <tex>p</tex> — программа для <tex>L \in \mathrm{RP}</tex>. Программу <tex>q</tex> для <tex>\mathrm{BPP}</tex> определим следующим образом:
q(x):
u <- p(x)
v <- p(x)
