BPP

From Традиция
Jump to navigation Jump to search

Класс сложности 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).

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

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

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

Класс сложности 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|)}\)

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

Класс сложности 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|)}\)

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

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

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

Error: No valid link was found at the end of line 2.

Ссылки[edit]


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