|
Персональные инструменты |
![]() |
||
|
![]() |
![]() PPМатериал из CustisWikiВерсия от 18:06, 6 декабря 2005; StasFomin (обсуждение | вклад) Это снимок страницы. Он включает старые, но не удалённые версии шаблонов и изображений. Класс сложности PP (Probability Polynomial-time) состоит из всех языков L для которых существует полиномиальная вероятностная машина Тьюринга M, такая что:
Можно показать, что класс PP, можно определить с «чуть пониженными» требованиями к распознающей ВМТ M:
или
Диаграмма «ближайших» классов сложности
Внимание! Эта статья была создана путем автоматического реплицирования из внутренней базы знаний компании Заказные Информ Системы. Любые правки этой статьи могут быть перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion». |
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
![]() |