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

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

Стас Фомин 02:10, 15 июня 2011 (MSD): Нет, не следует. ВМТ использует не больше полинома ленты. Ну и что? См. определение класса PSPACE, там более слабая модель — ДМТ

.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.