Комментарии — Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/BPP in PSPACE
Материал из DISCOPAL
BPP - класс предикатов, вычислимых за полиномиальное время вероятностной машиной Тьюринга (пусть и с ошибкой). Это означает, что вероятностная машина Тьюринга остановится за полиномиальное от длины входа время. За полиномиальное время она не успеет "изгадить" более полиномиального количества ленты. Отсюда следует доказываемое вложение.
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.