Сложностный класс BPP — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
==Определение класса PP==
 
==Определение класса PP==
Классом <tex>\mbox{PP}</tex> называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее результат совпадает с принадлежностью входа данным языкам и время ее работы ограничено полиномом от длины входа.
+
Классом <tex>\mbox{PP}</tex> называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее результат совпадает с принадлежностью входа данным языкам больше <tex>\frac{1}{2}</tex> и время ее работы ограничено полиномом от длины входа.
<tex>ZPP^{'} = \{ L | \exists m : L(m)=L, T(m(x)) \le poly(|x|) p(m(x) = ?) \le \frac{1}{2} \}</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>PP = \{L | \exists m : P(m(x) = [x \in L]) \g \frac{1}{2} \}</tex>
+
В этом определениях <tex>m</tex> - это [[Вероятностные машины Тьюринга | вероятностная машина Тьюринга]].
В этом определениях <tex>m</tex> - это [[Вероятностные машины Тьюринга | вероятностная машина Тьюринга]], время работы которой ограничено полиномом от длины входа.
 
  
 
==Определение класса BPP==
 
==Определение класса BPP==
<tex>BPP = \{L |{ }\exist m: T(m,x) = Poly(|x|) \and P(m(x) = [x \in L]) > 2/3 \}</tex><br>
+
Классом <tex>\mbox{BPP}</tex> называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее результат совпадает с принадлежностью входа данным языкам больше <tex>\frac{1}{2}</tex> и время ее работы ограничено полиномом от длины входа.
где <tex>m</tex> -- [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]].<br>
+
<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

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

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

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