Введение

В теории вычислительной сложности, ветви компьютерной науки, ограниченная по ошибке вероятностная полиномиальная сложность (BPP) – это класс задач, решаемых вероятностной машиной Тьюринга за полиномиальное время с вероятностью ошибки, не превышающей 1/3 для всех входных данных. BPP является одним из самых крупных практически значимых классов задач, что означает, что для большинства интересных задач из BPP существуют эффективные вероятностные алгоритмы, которые могут быть быстро выполнены на современных компьютерах. BPP также включает в себя P, класс задач, решаемых за полиномиальное время детерминированной машиной, поскольку детерминированная машина является частным случаем вероятностной машины. Алгоритм BPP (1 запуск) ≥ 2/3 ≤ 1/3 ≤ 1/3 ≥ 2/3 Алгоритм BPP (k запусков) > 1 − 2−ck < 2−ck < 2−ck > 1 − 2−ck для некоторой константы c > 0

Неформально, задача относится к классу BPP, если для неё существует алгоритм со следующими свойствами:
Он может использовать генератор случайных чисел и принимать случайные решения.
Гарантируется, что он завершится за полиномиальное время.
При любом запуске алгоритма вероятность выдачи неверного ответа, независимо от того, будет ли ответ "ДА" или "НЕТ", не превышает 1/3.

Проблемы

Все задачи из класса P очевидно также находятся в BPP. Однако многие задачи известны как принадлежащие BPP, но не известные как принадлежащие P. Число таких задач уменьшается, и существует предположение, что P = BPP. Долгое время одной из самых известных задач, принадлежащих BPP, но не принадлежащих P, была задача определения, является ли заданное число простым. Однако в статье 2002 года «PRIMES is in P» Маниндра Агравал и его студенты Нирадж Кайал и Нитин Саксена нашли детерминированный алгоритм полиномиального времени для решения этой задачи, тем самым доказав, что она принадлежит P.

Важным примером задачи в BPP (фактически в co-RP), принадлежность которой к P до сих пор не доказана, является проверка тождества полиномов – задача определения, равен ли полином тождественно нулевому полиному, при условии, что у вас есть доступ к значению полинома для любого заданного ввода, но нет доступа к его коэффициентам. Иными словами, существует ли такая подстановка значений переменных, при которой ненулевой полином, вычисленный на этих значениях, даст ненулевой результат? Достаточно присваивать каждой переменной значение, выбранное равномерно случайным образом из конечного множества, содержащего не менее d элементов, чтобы добиться ограниченной вероятности ошибки, где d – полная степень полинома.

Связанные классы

Если исключить доступ к случайности из определения BPP, мы получим класс сложности P. В определении класса, если заменить обычную машину Тьюринга квантовым компьютером, мы получим класс BQP. Добавление постселекции к BPP или разрешение вычислительным траекториям иметь разную длину приводит к классу BPPpath. Известно, что BPPpath содержит NP, и он содержится в своем квантовом аналоге PostBQP. Алгоритм Монте-Карло — это рандомизированный алгоритм, который с большой вероятностью выдает правильный ответ. Задачи в классе BPP имеют алгоритмы Монте-Карло с полиномиально ограниченным временем работы. Это противопоставляется алгоритму Лас-Вегаса, который является рандомизированным алгоритмом, выдающим либо правильный ответ, либо сообщение "неудача" с малой вероятностью. Алгоритмы Лас-Вегаса с полиномиально ограниченным временем работы используются для определения класса ZPP. Альтернативно, ZPP содержит вероятностные алгоритмы, которые всегда выдают правильный ответ и имеют ожидаемое полиномиальное время работы. Это более слабое утверждение, чем сказать, что это алгоритм с полиномиальным временем работы, поскольку он может выполняться за суперполиномиальное время, но с очень малой вероятностью.

Теоретические свойства сложности

Известно, что BPP замкнут относительно дополнения; то есть BPP = co BPP. BPP является низким для себя, что означает, что машина BPP, обладающая возможностью мгновенно решать задачи BPP (машина BPP-оракул), не более мощная, чем машина без этой дополнительной возможности. В символах, BPP<sup>BPP</sup> = BPP. Отношение между BPP и NP неизвестно: не известно, является ли BPP подмножеством NP, NP подмножеством BPP или ни то, ни другое. Если NP содержится в BPP, что считается маловероятным, поскольку это подразумевало бы практические решения для NP-полных задач, то NP = RP и PH ⊆ BPP. Известно, что RP является подмножеством BPP, а BPP является подмножеством PP. Неизвестно, являются ли эти два строгими подмножествами, поскольку мы даже не знаем, является ли P строгим подмножеством PSPACE. BPP содержится на втором уровне полиномиальной иерархии и, следовательно, содержится в PH. Более точно, теорема Сипсера — Лаутемана утверждает, что в результате P = NP приводит к P = BPP, поскольку PH схлопывается до P в этом случае. Таким образом, либо P = BPP, либо P ≠ NP, либо и то, и другое. Теорема Адлемана утверждает, что принадлежность к любому языку в BPP может быть определена семейством булевых схем полиномиального размера, что означает, что BPP содержится в P/poly. Действительно, как следствие доказательства этого факта, любой алгоритм BPP, работающий с входными данными ограниченной длины, может быть дерандомизирован в детерминированный алгоритм с использованием фиксированной строки случайных битов. Однако поиск этой строки может быть дорогостоящим. Некоторые слабые результаты о разделении для классов времени Монте-Карло были доказаны , см. также .

Свойства закрытия

Класс BPP замкнут относительно дополнения, объединения и пересечения.

Релятивизация

Относительно оракулов, мы знаем, что существуют оракулы A и B, такие, что PA = BPPA и PB ≠ BPPB. Более того, относительно случайного оракула с вероятностью 1, P = BPP, и BPP строго содержится в NP и co NP. Существует даже оракул, в котором BPP=EXPNP (и, следовательно, P<NP<BPP=EXP=NEXP), который можно итеративно построить следующим образом. Для фиксированной (релятивизированной) полной задачи ENP, оракул будет давать правильные ответы с высокой вероятностью, если запросить его экземпляром задачи, за которым следует случайная строка длиной kn (n – длина экземпляра; k – соответствующая небольшая константа). Начните с n=1. Для каждого экземпляра задачи длины n фиксируйте ответы оракула (см. лемму ниже), чтобы зафиксировать выход экземпляра. Далее, предоставьте выходы экземпляра для запросов, состоящих из экземпляра, за которым следует строка длины kn, а затем считайте выход для запросов длины ≤(k+1)n фиксированным и переходите к экземплярам длины n+1. Лемма: Для заданной задачи (в частности, кода оракульной машины и ограничения по времени) в релятивизированной ENP, для каждого частично сконструированного оракула и входа длины n, выход можно зафиксировать, указав 2O(n) ответов оракула. Доказательство: Машина моделируется, и ответы оракула (которые еще не фиксированы) фиксируются шаг за шагом. На каждый детерминированный шаг вычисления приходится не более одного запроса к оракулу. Для релятивизированного оракула NP, если возможно, зафиксируйте выход как "да", выбрав путь вычисления и зафиксировав ответы базового оракула; в противном случае фиксация не требуется, и в любом случае на шаг приходится не более 1 ответа базового оракула. Поскольку существует 2O(n) шагов, лемма следует из этого. Лемма гарантирует, что (для достаточно большого k) можно выполнить построение, оставив достаточно строк для релятивизированных ответов ENP. Кроме того, мы можем гарантировать, что для релятивизированной ENP достаточно линейного времени, даже для функциональных задач (если задан функциональный оракул и линейный размер вывода) и с экспоненциально малой (с линейным показателем) вероятностью ошибки. Также эта конструкция эффективна в том смысле, что, задав произвольный оракул A, мы можем сконструировать оракул B так, чтобы PA≤PB и EXPNPA=EXPNPB=BPPB. Кроме того, для оракула ZPP=EXP (и, следовательно, ZPP=BPP=EXP<NEXP), можно было бы зафиксировать ответы в релятивизированном вычислении E на специальный "неответ", тем самым гарантируя, что ложные ответы не будут даны.