Сложностный класс BPP — различия между версиями
(Новая страница: «==Определение класса PP== Классом <tex>\mbox{PP}</tex> называется множество языков, для которых сущес…») |
(→Определение класса PP) |
||
| Строка 1: | Строка 1: | ||
==Определение класса PP== | ==Определение класса PP== | ||
Классом <tex>\mbox{PP}</tex> называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее результат совпадает с принадлежностью входа данным языкам и время ее работы ограничено полиномом от длины входа. | Классом <tex>\mbox{PP}</tex> называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее результат совпадает с принадлежностью входа данным языкам и время ее работы ограничено полиномом от длины входа. | ||
| − | <tex>\mbox{PP} = \{L \mid \exists m: \mbox{P}(m(x) = | + | <tex>\mbox{PP} = \{L \mid \exists m: \mbox{P}(m(x) = [ x \in L ])\g \frac{1}{2}\}</tex> |
В этом определениях <tex>m</tex> - это [[Вероятностные машины Тьюринга | вероятностная машина Тьюринга]], время работы которой ограничено полиномом от длины входа. | В этом определениях <tex>m</tex> - это [[Вероятностные машины Тьюринга | вероятностная машина Тьюринга]], время работы которой ограничено полиномом от длины входа. | ||
==Определение класса BPP== | ==Определение класса BPP== | ||
Версия 10:13, 15 апреля 2010
Определение класса PP
Классом называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее результат совпадает с принадлежностью входа данным языкам и время ее работы ограничено полиномом от длины входа. В этом определениях - это вероятностная машина Тьюринга, время работы которой ограничено полиномом от длины входа.
