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 для которых существует

такие что:

\(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.

Диаграмма «ближайших» классов[править]

Ошибка: неверная ссылка в конце строки 2

Ссылки[править]


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