Обсуждение:Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/BPP in PSPACE — различия между версиями

Версия 11:40, 14 июня 2011

BPP - класс предикатов, вычислимых за полиномиальное время вероятностной машиной Тьюринга (пусть и с ошибкой). Это означает, что вероятностная машина Тьюринга остановится за полиномиальное от длины входа время. За полиномиальное время она не успеет "изгадить" более полиномиального количества ленты. Отсюда следует доказываемое вложение.