322
правки
Изменения
→См. также
{{Определение
|definition =
'''Вероятностная лента''' — бесконечная в одну сторону последовательность битов. Распределение битов на ленте , распределение которых подчиняется некоторому вероятностному закону (обычно считают, что биты в различных позициях независимы и вероятность нахождения <tex>0</tex> или <tex>1</tex> в каждой позиции равна <tex>1/2</tex>).
}}
{{Определение
|definition =
'''Вероятностной машиной Вероятностная машина Тьюринга''' будем называть машину (ВМТ) — детерминированная машина Тьюринга, имеющее доступ к имеющая вероятностную ленту. Переходы в ВМТ могут осуществляться с учетом информации, считанной с вероятностной лентеленты.
}}
<tex>R_i \in \Sigma</tex> как зависящие от <tex>i</tex> первых битов вероятностной ленты, <tex>\operatorname{P}(R_i) =\frac{1}{2^i} \cdot |\{s \bigm| |s| = Вероятностные сложностные классы ==i, s</tex> — префикс <tex>r \in R_i\}|</tex>.
}}
== Соотношение вероятностных классов См. также ==* [[Классы RP и coRP]]* [[Класс ZPP]]* [[Класс BPP]]
== Литература ==
* [http://www.cs.princeton.edu/theory/complexity/ Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach]