Класс BPP

Положение класса BPP в иерархии классов сложности.

В теории алгоритмов классом сложности 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 раз подряд, а в качестве результата возьмём результат большинства запусков, то вероятность ошибки упадёт до [math]\displaystyle{ \left(2 \sqrt{p(1-p)} \right)^n }[/math], а время станет равным O(n^k+1). Здесь n запусков машины рассматриваются как схема Бернулли с n испытаниями и вероятностью успеха 1-p, а формула, выражающая ошибку, — вероятность неудачи не менее чем в половине случаев. Если теперь запустить машину n² раз подряд, то время возрастёт до O(n^k+2), а вероятность ошибки упадёт до [math]\displaystyle{ \left(2 \sqrt{p(1-p)} \right)^{n^2} }[/math]. Таким образом, с ростом показателя многочлена, оценивающего время, точность растёт экспоненциально, и можно достичь любого нужного значения.

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

Запрос «Алгоритмы Монте-Карло» перенаправляется сюда; о численных методах см. Метод Монте-Карло.

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

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

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

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

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

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

[math]\displaystyle{ \mbox{BPP} \subseteq \mbox{BQP} }[/math]

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

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