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