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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «==Определение класса PP== Классом <tex>\mbox{PP}</tex> (от англ. ''probabilistic, polynomial'') называется множество…»)
 
м (rollbackEdits.php mass rollback)
 
(не показаны 2 промежуточные версии 2 участников)
Строка 4: Строка 4:
 
В этом определениях <tex>m</tex> - это [[Вероятностные машины Тьюринга | вероятностная машина Тьюринга]].
 
В этом определениях <tex>m</tex> - это [[Вероятностные машины Тьюринга | вероятностная машина Тьюринга]].
  
Но это очень широкий класс, <tex>\mbox{PH} \in \mbox{PP}</tex>. Поэтому вводится класс [[Сложностный класс BPP|<tex>\mbox{BPP}</tex>]].
+
Но это очень широкий класс, <tex>\mbox{PH} \subset \mbox{PP}</tex>. Поэтому вводится класс [[Сложностный класс BPP|<tex>\mbox{BPP}</tex>]].

Текущая версия на 19:35, 4 сентября 2022

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

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

Но это очень широкий класс, [math]\mbox{PH} \subset \mbox{PP}[/math]. Поэтому вводится класс [math]\mbox{BPP}[/math].