Сложностный класс BPP

Материал из Викиконспекты
Версия от 10:11, 15 апреля 2010; 192.168.0.2 (обсуждение) (Новая страница: «==Определение класса PP== Классом <tex>\mbox{PP}</tex> называется множество языков, для которых сущес…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Определение класса PP

Классом [math]\mbox{PP}[/math] называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее результат совпадает с принадлежностью входа данным языкам и время ее работы ограничено полиномом от длины входа. [math]\mbox{PP} = \{L \mid \exists m: \mbox{P}(m(x) = \[ x \in L\])\g \frac{1}{2}\}[/math] В этом определениях [math]m[/math] - это вероятностная машина Тьюринга, время работы которой ограничено полиномом от длины входа.

Определение класса BPP