BPP (сложность)
-
Определение и свойства класса BPP
- BPP — это класс задач, которые могут быть решены с помощью рандомизированных алгоритмов за полиномиальное время с ограниченной вероятностью ошибки.
- Задачи в BPP могут быть решены с использованием случайных чисел, но не требуют полного доступа к случайности.
- BPP включает в себя задачи, которые могут быть решены с помощью детерминированных алгоритмов, если известны все входные данные.
-
Связанные классы и теории
- BPP является подклассом P, если исключить доступ к случайности.
- Замена обычной машины Тьюринга на квантовый компьютер приводит к классу BQP.
- Добавление postselection к BPP дает класс BPPpath, который содержит NP.
- Алгоритмы Монте-Карло в BPP имеют полиномиальное время выполнения, в отличие от алгоритмов Лас-Вегаса, которые могут быть ошибочными с низкой вероятностью.
-
Свойства и релятивизация
- BPP замкнут при дополнении, объединении и пересечении.
- Относительно оракулов, существуют оракулы, которые делают PA = BPPA и PB ∈ BPPB.
- Для релятивизированного NP-оракула можно построить оракул с релятивизированными ответами ENP.
-
Дерандомизация и предположения
- Предполагается существование сильных генераторов псевдослучайных чисел, что подразумевает P = RP = BPP.
- Если EXPTIME не сокращается до MA, BPP содержится в i.o.-SUBEXP.
- Если экспоненциально-временная иерархия не разрушается, P = BPP.
Полный текст статьи: