Класс BPP

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

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

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

Число 1/3 в определении выбрано произвольно: если вместо него выбрать любое число p, строго меньшее 1/2, то получится тот же самый класс. Это верно, поскольку если есть машина Тьюринга, распознающая язык с вероятностью ошибки 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.

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

До 2002 года наиболее известной задачей, лежащей в классе BPP, было распознавание простоты числа. Был известен вероятностный тест простоты, дающий весьма хорошие результаты. Однако в 2002 году индийские математики Agrawal, Kayan и Saxena доказали более сильное утверждение: эта задача лежит к классе P, предъявив алгоритм, отвечающий на поставленный вопрос за время O(n12), где n — длина числа.

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home