Класс BPP

Класс BPP

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

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

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


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

\mbox{BPP} \subseteq \mbox{BQP}

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

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


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Полезное


Смотреть что такое "Класс BPP" в других словарях:

  • Класс PH — В теории алгоритмов классом сложности PH (от англ. polynomial hierarchy) называется объединение всех классов сложности из полиномиальной иерархии: Таким образом, предикат принадлежит классу PH, если существует такое k, что предикат принадлежит… …   Википедия

  • Класс RP — Будем считать, что язык L принадлежит классу RP («randomized polynomial class»  случайный полиномиальный), если он допускается вероятностной машиной Тьюринга M, для которой выполнены следующие условия: Если w не принадлежит L, то вероятность …   Википедия

  • BPP (значения) — Значения: англ. bits per pixel (количество бит на пиксель), также известно как глубина цвета Класс BPP  класс сложности в теории алгоритмов …   Википедия

  • BPP — Значения: англ. bits per pixel (количество бит на пиксель), также известно как глубина цвета Класс BPP  класс сложности в теории алгоритмов …   Википедия

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

  • Класс P — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отр …   Википедия

  • Класс BQP — Примерное положение BQP на карте классов NP, P, PSPACE. В теории алгоритмов классом сложности BQP (от англ.& …   Википедия

  • Класс PP — В теории сложности, PP является классом проблем, решаемых вероятностными машинами Тьюринга за полиномиальное время, с вероятностью ошибки менее 1/2. Аббревиатура PP обозначает «вероятностный полиномиальный по времени». Определение Язык L… …   Википедия

  • Класс сложности — В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Говоря более узко, классы сложности это множества предикатов (функций, получающих на вход слово и возвращающих ответ 0… …   Википедия

  • Класс NP — В теории алгоритмов классом NP (от англ. non deterministic polynomial) называют множество задач распознавания (англ.), решение которых при наличии некоторых дополнительных сведений (так называемого сертификата решения) можно «быстро» (за… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»