BPP

Класс сложности BPP (Bounded-Probability Polynomial-time) состоит из всех языков L для которых существует полиномиальная вероятностная машина Тьюринга M, такая что:

если $x\in L\,$, то $Pr\{ M(x)=1\} \geq 2/3\,$,

если $x\notin L\,$, то $Pr\{ M(x)=1\} \leq 1/3\,$.

Константа 1/3, ограничивающая вероятность ошибки, выбрана произвольно. Её можно заменить любой другой константой, меньшей 1/2. В самом деле, следующий простой прием позволяет добиться, чтобы вероятность правильного ответа была сколь угодно близка к 1. Для этого машина $M\,$ запускается $m\,$ раз на данном входе $x\,$, всякий раз с заново и независимо выбранным содержимым случайной ленты. Слово $x\,$ принимается или отвергается в зависимости от того, каких исходов, 0 или 1, больше среди $m\,$ ответов машины $M\,$. Легко показать, что вероятность ошибки убывает экспоненциально как функция от $m\,$ (при условии, что исходная вероятность ошибки машины $M\,$ ограничена произвольной константой, меньшей 1/2).

Варианты определения

Можно показать, что будут эквивалентны также следующие определения класса BPP:

«Строгое» определение

Класс сложности BPP состоит из всех языков L для которых существует полиномиальная вероятностная машина Тьюринга M, и полином p(*), такие что:

$x \in L \Rightarrow P[M(x)=1]\geq 1 - 2^{-p(|x|)}$

$x \notin L \Rightarrow P[M(x)=0]\geq 1 - 2^{-p(|x|)}$

«Свободное» определение

Класс сложности BPP состоит из всех языков L для которых существует

• полиномиально вычислимая функция $f:N\mapsto [0,1]$,
• полиномиальная вероятностная машина Тьюринга M,
• полином p(*),

такие что:

$x \in L \Rightarrow P[M(x)=1]\geq f(|x|) + \frac{1}{p(|x|)}$

$x \notin L \Rightarrow P[M(x)=1]< f(|x|) - \frac{1}{p(|x|)}$

Соотношения между классами

Очевидно, что P$\subseteq\,$BPP. Является ли это включение строгим — открытый вопрос теории сложности вычислений. Отметим также, что на данный момент о соотношении классов BPP и NP не известно ничего, кроме очевидного включения RP$\subseteq\,$NP$\cap\,$BPP.

Диаграмма «ближайших» классов

Ссылки

• BPP в custiswiki
• Курс Н. П. Варновского Понятия теории сложности вычислений

По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.