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