Класс BPP




Главная
Новости
Статьи
Ремонт
Каркасный дом
Несущие конструкции
Металлические конструкции
Прочность дорог
Дорожные материалы
Стальные конструкции
Грунтовые основания
Опорные сооружения




16.04.2021


16.04.2021


16.04.2021


12.04.2021


12.04.2021


12.04.2021


12.04.2021





Яндекс.Метрика

Класс BPP

06.01.2021

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

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

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

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

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

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

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

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


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

BPP ⊆ BQP {displaystyle {mbox{BPP}}subseteq {mbox{BQP}}}

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

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