Класс BPP

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

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

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

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

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

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

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

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

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

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

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

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

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

$\text{BPP}\subseteq <!--\; \subseteq \; -->\text{BQP}$${\mbox{BPP}}\subseteq {\mbox{BQP}}$ 

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

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