В теории алгоритмов классом сложности BPP (от англ. bounded-error, probabilistic, polynomial ) называется класс предикатов , быстро (за полиномиальное время) вычислимых и дающих ответ с высокой вероятностью (причём, жертвуя временем, можно добиться сколь угодно высокой точности ответа). Задачи, решаемые вероятностными методами и лежащие в BPP, возникают на практике очень часто.

Формальное определение

Классом BPP называется класс предикатов P(x) , вычислимых на вероятностных машинах Тьюринга (обычных машинах Тьюринга с лентой случайных чисел) за полиномиальное время с ошибкой не более ⅓. Это значит, что вычисляющая значение предиката вероятностная машина Тьюринга даст ответ за время, равное O(n ^k ) , где n — длина x , причём если правильный ответ 1, то машина выдаёт 1 с вероятностью как минимум ⅔, и наоборот. Множество слов, на которых P(x) возвращает 1, называется языком , распознаваемым предикатом P(x) .

Число ⅓ в определении выбрано произвольно: если вместо него выбрать любое число p , строго меньшее ½, то получится тот же самый класс. Это верно, поскольку если есть машина Тьюринга, распознающая язык с вероятностью ошибки p за время O(n ^k ) , то точность можно сколь угодно хорошо улучшить за счёт относительно небольшого прироста времени. Если мы запустим машину n раз подряд, а в качестве результата возьмём результат большинства запусков, то вероятность ошибки упадёт до ${\displaystyle \left(2{\sqrt {p(1-p)}}\right)^{n}}$ , а время станет равным O(n ^k+1 ) . Здесь n запусков машины рассматриваются как схема Бернулли с n испытаниями и вероятностью успеха 1-p , а формула, выражающая ошибку, — вероятность неудачи не менее чем в половине случаев. Если теперь запустить машину n ² раз подряд, то время возрастёт до O(n ^k+2 ) , а вероятность ошибки упадёт до ${\displaystyle \left(2{\sqrt {p(1-p)}}\right)^{n^{2}}}$ . Таким образом, с ростом показателя многочлена, оценивающего время, точность растёт экспоненциально , и можно достичь любого нужного значения.

Алгоритмы Монте-Карло

Вероятностный алгоритм ${\displaystyle {\mathcal {A}}}$ принимает язык ${\displaystyle L}$ по стандарту Монте-Карло, если вероятность ошибки алгоритма не превосходит ${\displaystyle 1/3}$ . То есть, ${\displaystyle \mathbb {P} ({\mathcal {A}}(x)=P(x))\geq 2/3}$ , где ${\displaystyle P(x)}$ — предикат принадлежности слова ${\displaystyle x}$ языку ${\displaystyle L}$ . Таким образом, класс BPP образуют предикаты такие что для них существует полиномиальный вероятностный алгоритм, принимающий их язык по стандарту Монте-Карло. Такие алгоритмы также называют алгоритмами Монте-Карло.

Связь с алгоритмами Лас-Вегаса

Пусть ${\displaystyle {\mathcal {B}}}$ алгоритм Монте-Карло с временной сложностью ${\displaystyle f(n)}$ , где - длина входа. Также примем за ${\displaystyle p(n)}$ нижнюю границу вероятности того, что алгоритм Лас-Вегаса ${\displaystyle {\mathcal {A}}}$ даст корректный результат, а за ${\displaystyle {\mathcal {C}}}$ алгоритм с временной сложностью ${\displaystyle g(n)}$ , проверяющий результат ${\displaystyle {\mathcal {A}}}$ на достоверность. В таком случае существует алгоритм ${\displaystyle {\mathcal {A}}}$ с ожидаемой временной сложностью ${\displaystyle (f(n)+g(n))/p(n)}$ . Для доказательства представим, что ${\displaystyle {\mathcal {A}}}$ вызывает ${\displaystyle {\mathcal {B}}}$ и ${\displaystyle {\mathcal {C}}}$ до тех пор, пока ${\displaystyle {\mathcal {C}}}$ не подтвердит корректность результата. Тогда время работы одной итерации такой процедуры составит ${\displaystyle f(n)+g(n)}$ . Вероятность же того, что будет повторено ${\displaystyle k}$ итераций равна ${\displaystyle (1-p(n))^{k-1}\cdot p(n)}$ , а значит, ожидаемое количество итераций равно ${\displaystyle \sum _{k=1}^{\infty }k\cdot (1-p(n))^{k-1}\cdot p(n)=1/p(n)}$ , исходя из того, что ${\displaystyle \sum _{k=1}^{\infty }k\cdot x^{k}=x/(1-x)^{2}}$ .

Отношения с другими классами

Сам BPP замкнут относительно дополнения. Класс P включён в BPP, поскольку он даёт ответ за полиномиальное время с нулевой ошибкой. BPP включён в класс ${\displaystyle \Sigma _{2}^{p}\cap \Pi _{2}^{p}}$ полиномиальной иерархии и, как следствие, включён в PH и PSPACE . Кроме того, известно включение BPP в .

Квантовым аналогом класса BPP (другими словами, расширением класса BPP на квантовые компьютеры ) является класс BQP .

${\displaystyle {\mbox{BPP}}\subseteq {\mbox{BQP}}}$

Другие свойства

До 2002 года одной из наиболее известных задач, лежащих в классе BPP, была задача распознавания простоты числа, для которой существовало несколько различных полиномиальных вероятностных алгоритмов, таких как тест Миллера-Рабина , но ни одного детерминированного. Однако, в 2002 году детерминированный полиномиальный алгоритм был найден индийскими математиками Agrawal, Kayan и Saxena, которые таким образом доказали, что задача распознавания простоты числа лежит в классе P . Предложенный ими алгоритм AKS (названный по первым буквам их фамилий) распознает простоту числа длины n за время O(n ⁴ ) .