Обсуждение:Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/BPP in PSPACE — различия между версиями
Материал из DISCOPAL
(Новая страница: «BPP - класс предикатов, вычислимых '''за полиномиальное время''' вероятностной машиной Тьюрин...») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
BPP - класс предикатов, вычислимых '''за полиномиальное время''' вероятностной машиной Тьюринга (пусть и с ошибкой). Это означает, что вероятностная машина Тьюринга остановится за полиномиальное от длины входа время. За полиномиальное время она не успеет "изгадить" более полиномиального количества ленты. Отсюда следует доказываемое вложение. | BPP - класс предикатов, вычислимых '''за полиномиальное время''' вероятностной машиной Тьюринга (пусть и с ошибкой). Это означает, что вероятностная машина Тьюринга остановится за полиномиальное от длины входа время. За полиномиальное время она не успеет "изгадить" более полиномиального количества ленты. Отсюда следует доказываемое вложение. | ||
| + | |||
| + | {{remark|[[Участник:StasFomin|Стас Фомин]] 02:10, 15 июня 2011 (MSD): Нет, не следует. ВМТ использует не больше полинома ленты. Ну и что? См. определение класса [[PSPACE]], там более слабая модель — ДМТ}}. | ||
Текущая версия на 22:10, 14 июня 2011
BPP - класс предикатов, вычислимых за полиномиальное время вероятностной машиной Тьюринга (пусть и с ошибкой). Это означает, что вероятностная машина Тьюринга остановится за полиномиальное от длины входа время. За полиномиальное время она не успеет "изгадить" более полиномиального количества ленты. Отсюда следует доказываемое вложение.
Стас Фомин 02:10, 15 июня 2011 (MSD): Нет, не следует. ВМТ использует не больше полинома ленты. Ну и что? См. определение класса PSPACE, там более слабая модель — ДМТ
.