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