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.

Ссылки

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