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

Материал из DISCOPAL
Перейти к: навигация, поиск

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

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

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

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

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