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