БПП (сложность) - BPP (complexity)

В теории сложности вычислений , ограниченные ошибки вероятностное полиномиальное время ( BPP ) является класс задач принятия решений разрешимо с помощью вероятностной машины Тьюринга в полиномиальное время с погрешностью вероятностью отделенной от 1/3 всех случаев. BPP - один из крупнейших практических классов проблем, а это означает, что большинство проблем, представляющих интерес для BPP, имеют эффективные вероятностные алгоритмы, которые можно быстро запустить на реальных современных машинах. BPP также содержит P , класс задач, решаемых за полиномиальное время с помощью детерминированной машины, поскольку детерминированная машина является частным случаем вероятностной машины.

Алгоритм BPP (1 запуск)
Отвечать произведено Правильный ответ	да	Нет
да	≥ 2/3	≤ 1/3
Нет	≤ 1/3	≥ 2/3
Алгоритм BPP ( k запусков)
Отвечать произведено Правильный ответ	да	Нет
да	> 1-2 ^{- ск}	<2 ^{- ck}
Нет	<2 ^{- ck}	> 1-2 ^{- ск}
для некоторой постоянной c > 0

Неформально проблема заключается в BPP, если для нее существует алгоритм, обладающий следующими свойствами:

Разрешено подбрасывать монеты и принимать случайные решения.
Гарантированно работает за полиномиальное время
При любом заданном запуске алгоритма вероятность того, что он даст неправильный ответ, составляет не более 1/3, независимо от того, ДА или НЕТ.

Определение

Язык L принадлежит BPP тогда и только тогда, когда существует вероятностная машина Тьюринга M , такая что

M работает за полиномиальное время на всех входах
Для всех х в L , М выходов 1 с вероятностью , большей или равной 2/3
Для всех x, не входящих в L , M выдает 1 с вероятностью, меньшей или равной 1/3.

В отличие от класса сложности ZPP , машина M должна работать в течение полиномиального времени на всех входах, независимо от результата случайных подбрасываний монеты.

В качестве альтернативы BPP может быть определен с использованием только детерминированных машин Тьюринга. Язык L принадлежит BPP тогда и только тогда, когда существует многочлен p и детерминированная машина Тьюринга M , такие что

M работает за полиномиальное время на всех входах
Для всех x в L доля строк y длины p (| x |), которым удовлетворяют , больше или равна 2/3 ${\ Displaystyle М (х, у) = 1}$
Для всех x, не принадлежащих L , доля строк y длины p (| x |), которым удовлетворяют , меньше или равна 1/3 ${\ Displaystyle М (х, у) = 1}$

В этом определении строка y соответствует результату случайных подбрасываний монеты, которые могла бы сделать вероятностная машина Тьюринга. Для некоторых приложений это определение предпочтительнее, поскольку в нем не упоминаются вероятностные машины Тьюринга.

На практике вероятность ошибки 1/3 может быть неприемлемой, однако выбор 1/3 в определении является произвольным. Изменение определения для использования любой константы от 0 до 1/2 (исключая) вместо 1/3 не изменит результирующий набор BPP . Например, если определить класс с ограничением, что алгоритм может ошибаться с вероятностью не более 1/2 ¹⁰⁰ , это приведет к тому же классу проблем. Вероятность ошибки даже не обязательно должна быть постоянной: один и тот же класс проблем определяется тем, что допускает ошибку, равную 1/2 - n ^{- c,} с одной стороны, или требуя ошибку, равную 2 ^{- n ^c,} с другой стороны. , где c - любая положительная константа, а n - длина ввода. Эта гибкость в выборе вероятности ошибки основана на идее многократного выполнения подверженного ошибкам алгоритма и использования большинства результатов прогонов для получения более точного алгоритма. Вероятность того, что большинство прогонов ошибочны, падает экспоненциально из-за границы Чернова .

Проблемы

Нерешенная проблема в информатике :

${\ Displaystyle {\ mathsf {P}} {\ overset {?} {=}} {\ mathsf {BPP}}}$

(больше нерешенных проблем в информатике)

Очевидно, что все проблемы в P также относятся к BPP . Тем не менее, многие проблемы, как известно, быть в БПП , но не известно, что в P . Количество таких проблем уменьшается, и предполагается, что P = BPP .

В течение долгого времени одной из самых известных проблем, связанных с BPP, но неизвестных о принадлежности к P, была проблема определения того, является ли данное число простым . Тем не менее, в 2002 году бумажного PRIMES в P , Маниндр Агравал и его ученики Neeraj Kayal и Нитин Саксен нашли детерминированный полиномиальный алгоритм для этой проблемы, тем самым показывая , что он находится в P .

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

Родственные классы

Если доступ к хаотичности удаляются из определения БПП , мы получаем класс сложности P . В определении класса, если заменить обычную машину Тьюринга с квантовым компьютером , мы получаем класс BQP .

Добавление поствыбора к BPP или разрешение путей вычислений иметь разную длину дает _путь класса BPP . Известно, что _путьBPP содержит NP , и он содержится в его квантовом аналоге PostBQP .

Монте - Карло алгоритм является рандомизированное алгоритм , который, вероятно, будет правильным. Задачи класса BPP имеют алгоритмы Монте-Карло с полиномиально ограниченным временем выполнения. Это сравнивается с алгоритмом Лас-Вегаса, который представляет собой рандомизированный алгоритм, который либо выводит правильный ответ, либо выводит «сбой» с низкой вероятностью. Для определения класса ZPP используются алгоритмы Лас-Вегаса с полиномиально ограниченным временем выполнения . В качестве альтернативы ZPP содержит вероятностные алгоритмы, которые всегда верны и имеют ожидаемое полиномиальное время выполнения. Это слабее, чем сказать, что это алгоритм с полиномиальным временем, поскольку он может работать в течение суперполиномиального времени, но с очень низкой вероятностью.

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

BPP по отношению к другим классам вероятностной сложности ( ZPP , RP , co-RP, BQP , PP ), которые обобщают P в рамках PSPACE . Неизвестно, являются ли какие-либо из этих условий строгими.

Известно, что БПП закрывается при дополнении ; то есть BPP = co-BPP . BPP является низким для себя, а это означает , что BPP машина с силой , чтобы решить BPP проблему мгновенно (а BPP оракул машина ) не какой - либо более мощным , чем машины без этой дополнительной мощности. В символах BPP ^BPP = BPP .

Отношения между БППАМИ и NP неизвестно: неизвестно , является ли БПП является подмножеством из НП , НП является подмножеством БПП или ни. Если 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, либо и то, и другое. ${\ Displaystyle {\ mathsf {BPP}} \ substeq \ Sigma _ {2} \ cap \ Pi _ {2}}$

Теорема Адлемана утверждает, что членство в любом языке в BPP может быть определено семейством логических схем полиномиального размера , что означает, что BPP содержится в P / poly . Действительно, как следствие доказательства этого факта, любой алгоритм BPP , работающий на входах ограниченной длины, может быть дерандомизирован в детерминированный алгоритм с использованием фиксированной строки случайных битов. Однако поиск этой строки может оказаться дорогостоящим. Некоторые слабые результаты разделения для классов времени Монте-Карло были доказаны Karpinski & Verbeek (1987a) , см. Также Karpinski & Verbeek (1987b) .

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

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

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

Относительно оракулов, мы знаем , что существуют оракулы А и В, такие , что P ^A = BPP ^A и P ^B ≠ BPP ^B . Более того, относительно случайного оракула с вероятностью 1, P = BPP и BPP строго содержится в NP и co-NP .

Существует даже оракул, в котором BPP = EXP ^NP (и, следовательно, P <NP <BPP = EXP = NEXP), который можно итеративно построить следующим образом. Для фиксированной E ^NP (релятивизированной) полной задачи оракул с высокой вероятностью даст правильные ответы, если будет запрошен экземпляр проблемы, за которым следует случайная строка длины kn ( n - длина экземпляра; k - подходящая малая константа). Начнем с n = 1. Для каждого экземпляра задачи длины n исправьте ответы оракула (см. Лемму ниже), чтобы исправить вывод экземпляра. Затем предоставьте выходные данные экземпляра для запросов, состоящих из экземпляра, за которым следует строка kn -length, а затем обработайте выходные данные для запросов длины ≤ ( k +1) n как фиксированные и продолжите с экземплярами длины n +1.

Лемма: Учитывая проблему (в частности, машинный код оракула и ограничение по времени) в релятивизированном E ^NP , для каждого частично построенного оракула и ввода длины n , выход может быть исправлен путем указания 2 ^{O ( n )} ответов оракула.
Доказательство: машина смоделирована, и ответы оракула (которые еще не исправлены) фиксируются шаг за шагом. На каждый шаг детерминированных вычислений приходится не более одного запроса оракула. Для релятивизированного NP-оракула, если возможно, зафиксируйте вывод как «да», выбрав путь вычисления и зафиксировав ответы базового оракула; в противном случае исправление не требуется, и в любом случае существует не более 1 ответа базового оракула на шаг. Поскольку существует 2 ^{O ( n )} шагов, лемма следует.

Лемма гарантирует, что (для достаточно большого k ) можно выполнить построение, оставив достаточно строк для релятивизированных ответов E ^NP . Кроме того, мы можем гарантировать, что для релятивизированного E ^NP линейного времени достаточно, даже для функциональных задач (если задан функциональный оракул и линейный выходной размер) и с экспоненциально малой (с линейной экспонентой) вероятностью ошибки. Кроме того , эта конструкция является эффективным в том , что задано произвольное оракула А мы можем организовать оракула B , чтобы иметь P ^A ≤P ^B и EXP ^{NP ^A} = EXP ^{NP ^B} = BPP ^B . Кроме того, для оракула ZPP = EXP (и, следовательно, ZPP = BPP = EXP <NEXP), можно было бы исправить ответы в релятивизированном вычислении E на специальный неответ, таким образом гарантируя, что не будут даны ложные ответы.

Дерандомизация

Существование некоторых сильного числа генераторов псевдослучайных является предположение , большинство специалистов этой области. Эта гипотеза подразумевает, что случайность не дает дополнительных вычислительных мощностей для вычисления за полиномиальное время, то есть P = RP = BPP . Обратите внимание, что обычных генераторов недостаточно, чтобы показать этот результат; любой вероятностный алгоритм, реализованный с использованием типичного генератора случайных чисел, всегда будет давать неверные результаты на определенных входных данных, независимо от начального числа (хотя эти входные данные могут быть редкими).

Ласло Бабай , Ланс Фортноу , Ноам Нисан и Ави Вигдерсон показали, что если EXPTIME не превратится в MA , BPP содержится в

{\ displaystyle {\textf {io-SUBEXP}} = \ bigcap \ nolimits _ {\ varepsilon> 0} {\textf {io-DTIME}} \ left (2 ^ {n ^ {\ varepsilon}} \ right). }

Класс io-SUBEXP , который обозначает бесконечно часто SUBEXP , содержит задачи, которые имеют алгоритмы субэкспоненциального времени для бесконечно большого количества входных данных. Они также показали, что P = BPP, если иерархия экспоненциального времени, которая определяется в терминах полиномиальной иерархии и E как E ^PH , схлопывается до E ; однако учтите, что обычно предполагается, что иерархия экспоненциального времени не разрушится.

Рассел Импальяццо и Ави Вигдерсон показали, что если есть проблема в E , где

{\ displaystyle {\ mathsf {E}} = {\ mathsf {DTIME}} \ left (2 ^ {O (n)} \ right),}

имеет схемную сложность 2 ^{Ω ( n ),} то P = BPP .

Languages

In other projects

БПП (сложность) - BPP (complexity)

СОДЕРЖАНИЕ