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