322
правки
Изменения
Новая страница: «{{В разработке}} Здесь будет введение. == Основные определения == {{Определение |definition = '''Ве...»
{{В разработке}}
Здесь будет введение.
== Основные определения ==
{{Определение
|definition =
'''Вероятностная лента''' — бесконечная последовательность битов. Распределение битов на ленте подчиняется некоторому вероятностному закону (обычно считают, что вероятность нахождения <tex>0</tex> или <tex>1</tex> в каждой позиции равна <tex>1/2</tex>).
}}
{{Определение
|definition =
'''Вероятностной машиной Тьюринга''' будем называть машину Тьюринга, имеющее доступ к вероятностной ленте.
}}
При интерпретации вероятностной машины Тьюринга как программы, обращение к очередному биту можно трактовать как вызов специальной функции ''random''(). При этом также будем предполагать, что вероятностная лента является неявным аргументом для программы, т.е. <tex>p(x) = p(x, r)</tex>, где <tex>r</tex> — вероятностная лента.
Здесь будет теорема о том, что утверждения, связанные с ВМТ, являются событиями.
+ матожидание будем считать по пространству лент
== Вероятностные сложностные классы ==
Теперь введем некоторые сложностные классы.
{{Определение
|definition =
<tex>\mathrm{ZPP}</tex> (от ''zero-error probabilistic polynomial'') — множество языков, для которых <tex>\exists p \forall x</tex>:
1) <tex>\operatorname{P}(p(x) \ne [x \in L]) = 0</tex>;<br>
2) <tex>\operatorname{E}(\operatorname{T}(p(x))) = poly(|x|)</tex>.<br>
}}
{{Определение
|definition =
<tex>\mathrm{RP}</tex> (от ''randomized polynomial'') — множество языков, для которых <tex>\exists p \forall x</tex>:
1) <tex>x \notin L \Rightarrow p(x) = 0</tex>;<br>
2) <tex>x \in L \Rightarrow \operatorname{P}(p(x) = 1) \ge 1/2</tex>;<br>
3) <tex>\forall r \operatorname{T}(p(x)) \le poly(|x|).</tex>
}}
Заметим, что константа в пункте 2 определения <tex>\mathrm{RP}</tex> может быть заменена на любую другую из промежутка <tex>(0, 1)</tex>, поскольку требуемой вероятности можно добиться множественным запуском программы.
<tex>\mathrm{RP}</tex> можно рассматривать как вероятностный аналог класса <tex>\mathrm{NP}</tex>, предполагая, что вероятность угадать сертификат в случае его существования не менее <tex>1/2</tex>.
== Литература ==
Здесь будет введение.
== Основные определения ==
{{Определение
|definition =
'''Вероятностная лента''' — бесконечная последовательность битов. Распределение битов на ленте подчиняется некоторому вероятностному закону (обычно считают, что вероятность нахождения <tex>0</tex> или <tex>1</tex> в каждой позиции равна <tex>1/2</tex>).
}}
{{Определение
|definition =
'''Вероятностной машиной Тьюринга''' будем называть машину Тьюринга, имеющее доступ к вероятностной ленте.
}}
При интерпретации вероятностной машины Тьюринга как программы, обращение к очередному биту можно трактовать как вызов специальной функции ''random''(). При этом также будем предполагать, что вероятностная лента является неявным аргументом для программы, т.е. <tex>p(x) = p(x, r)</tex>, где <tex>r</tex> — вероятностная лента.
Здесь будет теорема о том, что утверждения, связанные с ВМТ, являются событиями.
+ матожидание будем считать по пространству лент
== Вероятностные сложностные классы ==
Теперь введем некоторые сложностные классы.
{{Определение
|definition =
<tex>\mathrm{ZPP}</tex> (от ''zero-error probabilistic polynomial'') — множество языков, для которых <tex>\exists p \forall x</tex>:
1) <tex>\operatorname{P}(p(x) \ne [x \in L]) = 0</tex>;<br>
2) <tex>\operatorname{E}(\operatorname{T}(p(x))) = poly(|x|)</tex>.<br>
}}
{{Определение
|definition =
<tex>\mathrm{RP}</tex> (от ''randomized polynomial'') — множество языков, для которых <tex>\exists p \forall x</tex>:
1) <tex>x \notin L \Rightarrow p(x) = 0</tex>;<br>
2) <tex>x \in L \Rightarrow \operatorname{P}(p(x) = 1) \ge 1/2</tex>;<br>
3) <tex>\forall r \operatorname{T}(p(x)) \le poly(|x|).</tex>
}}
Заметим, что константа в пункте 2 определения <tex>\mathrm{RP}</tex> может быть заменена на любую другую из промежутка <tex>(0, 1)</tex>, поскольку требуемой вероятности можно добиться множественным запуском программы.
<tex>\mathrm{RP}</tex> можно рассматривать как вероятностный аналог класса <tex>\mathrm{NP}</tex>, предполагая, что вероятность угадать сертификат в случае его существования не менее <tex>1/2</tex>.
== Литература ==
