Обсуждение:Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/BPP in PSPACE — различия между версиями
Материал из DISCOPAL
(Новая страница: «BPP - класс предикатов, вычислимых '''за полиномиальное время''' вероятностной машиной Тьюрин...») |
(нет различий)
|
Версия 11:40, 14 июня 2011
BPP - класс предикатов, вычислимых за полиномиальное время вероятностной машиной Тьюринга (пусть и с ошибкой). Это означает, что вероятностная машина Тьюринга остановится за полиномиальное от длины входа время. За полиномиальное время она не успеет "изгадить" более полиномиального количества ленты. Отсюда следует доказываемое вложение.