322
правки
Изменения
Нет описания правки
{{В разработке}}
[[Категория: Теория сложности]]
== Основные определения ==
|definition =
'''Вероятностной машиной Тьюринга''' будем называть машину Тьюринга, имеющее доступ к вероятностной ленте.
}}
При интерпретации вероятностной машины Тьюринга как программы, обращение к очередному биту можно трактовать как вызов специальной функции ''random''(). При этом также будем предполагать, что вероятностная лента является неявным аргументом для программы, т.е. <tex>p(x) = p(x, r)</tex>, где <tex>r</tex> — вероятностная лента.
<br>
В дальнейшем все вероятностные соображения будут относиться к пространству вероятностных лент <tex>r</tex>, вход же программы <tex>x</tex> будем считать фиксированным.
Здесь будет теорема о том, что утверждения, связанные с ВМТ, являются событиями.
== Вероятностные сложностные классы ==
{{Определение
|definition =
...
<br>
2. Покажем, что <tex>\mathrm{RP} \subset \mathrm{NP}</tex>. Если в разрешающей программе для <tex>L \in \mathrm{RP}</tex> заменить все вызовы ''random''() на недетерминированный выбор, то получим программу с ограничениями <tex>\mathrm{NP}</tex>, разрешающую <tex>L</tex>.<br>Покажем, что <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> оказалось больше.
<br>
Теперь докажем, что <tex>\mathrm{NP} \subset \mathrm{PP}</tex>. Приведем программу <tex>q</tex> с ограничениями класса <tex>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> будет выглядеть следующим образом:
