BPP
Класс сложности BPP (Bounded-Probability Polynomial-time) состоит из всех языков L для которых существует полиномиальная вероятностная машина Тьюринга M, такая что:
если , то ,
если , то .
Константа 1/3, ограничивающая вероятность ошибки, выбрана произвольно. Её можно заменить любой другой константой, меньшей 1/2. В самом деле, следующий простой прием позволяет добиться, чтобы вероятность правильного ответа была сколь угодно близка к 1. Для этого машина запускается раз на данном входе , всякий раз с заново и независимо выбранным содержимым случайной ленты. Слово принимается или отвергается в зависимости от того, каких исходов, 0 или 1, больше среди ответов машины . Легко показать, что вероятность ошибки убывает экспоненциально как функция от (при условии, что исходная вероятность ошибки машины ограничена произвольной константой, меньшей 1/2).
Варианты определения[править | править код]
Можно показать, что будут эквивалентны также следующие определения класса BPP:
«Строгое» определение[править | править код]
Класс сложности BPP состоит из всех языков L для которых существует полиномиальная вероятностная машина Тьюринга M, и полином p(*), такие что:
«Свободное» определение[править | править код]
Класс сложности BPP состоит из всех языков L для которых существует
- полиномиально вычислимая функция ,
- полиномиальная вероятностная машина Тьюринга M,
- полином p(*),
такие что:
Соотношения между классами[править | править код]
Очевидно, что PBPP. Является ли это включение строгим — открытый вопрос теории сложности вычислений. Отметим также, что на данный момент о соотношении классов BPP и NP не известно ничего, кроме очевидного включения RPNPBPP.
Диаграмма «ближайших» классов[править | править код]
Ссылки[править | править код]
- BPP в custiswiki
- Курс Н. П. Варновского Понятия теории сложности вычислений
По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.