БПП (сложность)

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

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

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

Определение

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

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

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

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

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

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

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

Проблемы

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

⁠ ⁠

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

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

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

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

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

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

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

Добавление постселекции к BPP или разрешение вычислительным путям иметь различную длину дает класс BPP _path . ^[3] Известно, что BPP _{path содержит}NP , и он содержится в своем квантовом аналоге PostBQP .

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

Свойства теории сложности

Включения классов сложности, включая P , NP , co-NP , BPP, P/poly , PH и PSPACE

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

Связь между BPP и NP неизвестна: неизвестно, является ли BPP подмножеством NP , NP является подмножеством BPP или ни то, ни другое. Если NP содержится в BPP , что считается маловероятным, поскольку это подразумевало бы практические решения для NP-полных задач, то NP = RP и PH ⊆ BPP . [ ^4]

Известно, что RP является подмножеством BPP , а BPP является подмножеством PP . Неизвестно, являются ли эти два строгими подмножествами, поскольку мы даже не знаем, является ли P строгим подмножеством PSPACE . BPP содержится во втором уровне полиномиальной иерархии , и поэтому оно содержится в PH . Точнее, теорема Сипсера–Лаутемана утверждает, что . В результате P = NP приводит к P = BPP, поскольку PH в этом случае схлопывается до P. Таким образом, либо P = BPP , либо P ≠ NP , либо и то , и другое. ${\mathsf {BPP}}\subseteq \Сигма _{2}\cap \Пи _{2}$

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

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

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

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

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

Существует даже оракул, в котором ⁠ ⁠ ${\mathsf {BPP}}={\mathsf {EXP}}^{\mathsf {NP}}$ (и, следовательно, ⁠ ⁠ ${\mathsf {P<NP<BPP=EXP=NEXP}}$ ), ^[7] который может быть итеративно построен следующим образом. Для фиксированной E ^NP (релятивизированной) полной проблемы оракул с высокой вероятностью даст правильные ответы, если запросить экземпляр проблемы, за которым следует случайная строка длины kn ( n — длина экземпляра; k — подходящая малая константа). Начните с n = 1. Для каждого экземпляра проблемы длиной n исправьте ответы оракула (см. лемму ниже), чтобы исправить вывод экземпляра. Затем предоставьте вывод экземпляра для запросов, состоящих из экземпляра, за которым следует строка длины kn , а затем обработайте вывод для запросов длиной ≤( k +1) n как фиксированный и продолжите с экземплярами длиной n +1.

Лемма — Если задана задача (в частности, машинный код оракула и ограничение по времени) в релятивизированном $E NP$ , для каждого частично построенного оракула и входных данных длины n выход можно исправить, указав 2 ^{O ( n )} ответов оракула.

Доказательство

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

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

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

Существование некоторых сильных генераторов псевдослучайных чисел предполагается большинством экспертов в этой области. Такие генераторы могли бы заменить истинные случайные числа в любом рандомизированном алгоритме полиномиального времени, производя неразличимые результаты. Предположение о том, что эти генераторы существуют, подразумевает, что случайность не дает дополнительной вычислительной мощности вычислениям полиномиального времени, то есть P = RP = BPP . Более того, предположение о том, что P = BPP, в некотором смысле эквивалентно существованию сильных генераторов псевдослучайных чисел. ^[8]

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

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

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

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

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

имеет сложность схемы 2 ^{Ω( n )} , тогда P = BPP . ^[10]

Смотрите также

Ссылки

^ Валентин Кабанец, CMPT 710 - Теория сложности: Лекция 16, 28 октября 2003 г.
^ Мадху Судан и Шиен Джин Онг. Массачусетский технологический институт: 6.841/18.405J Продвинутая теория сложности: Лекция 6: Рандомизированные алгоритмы, свойства BPP. 26 февраля 2003 г.
^ «Зоопарк сложности:B — Зоопарк сложности».
↑ Лэнс Фортнау, Вытягивая квантовость, 20 декабря 2005 г.
^ Адлеман, Л. М. (1978). «Две теоремы о случайном полиномиальном времени». Труды девятнадцатого ежегодного симпозиума IEEE по основам вычислений . С. 75–83.
^ Беннетт, Чарльз Х.; Гилл, Джон (1981), «Относительно случайного оракула A, P^A!= NP^A!= co-NP^A с вероятностью 1», SIAM Journal on Computing , 10 (1): 96–113, doi :10.1137/0210008, ISSN 1095-7111
^ Хеллер, Ганс (1986), «О релятивизированных экспоненциальных и вероятностных классах сложности», Информация и управление , 71 (3): 231–243, doi : 10.1016/S0019-9958(86)80012-2
^ Goldreich, Oded (2011). "In a World of P=BPP" (PDF) . В Goldreich, Oded (ред.). Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman . Lecture Notes in Computer Science. Vol. 6650. Springer. pp. 191–232. doi :10.1007/978-3-642-22670-0_20.
^ Бабай, Ласло; Фортнау, Лэнс; Нисан, Ноам; Вигдерсон, Ави (1993). « BPP имеет субэкспоненциальное время моделирования, если EXPTIME не имеет публикуемых доказательств». Computational Complexity . 3 (4): 307–318. doi :10.1007/bf01275486. S2CID 14802332.
^ Рассел Импальяццо и Ави Вигдерсон (1997). " P = BPP, если E требует экспоненциальных схем: дерандомизация леммы XOR". Труды Двадцать девятого ежегодного симпозиума ACM по теории вычислений , стр. 220–229. doi :10.1145/258533.258590

Валентин Кабанец (2003). "CMPT 710 – Теория сложности: Лекция 16". Университет Саймона Фрейзера .
Христос Пападимитриу (1993). Computational Complexity (1-е изд.). Эддисон Уэсли. ISBN 0-201-53082-1.Страницы 257–259 раздела 11.3: Случайные источники. Страницы 269–271 раздела 11.4: Сложность схемы.
Майкл Сипсер (1997). Введение в теорию вычислений . PWS Publishing. ISBN 0-534-94728-X.Раздел 10.2.1: Класс BPP, стр. 336–339.
Карпински, Марек ; Вербек, Рутгер (1987a). «Случайность, доказуемость и разделение времени и пространства Монте-Карло». В Börger, Egon (ред.). Теория вычислений и логика, памяти Дитера Реддинга . Конспект лекций по информатике. Том 270. Springer. С. 189–207. doi :10.1007/3-540-18170-9_166.
Карпински, Марек ; Вербек, Рутгер (1987b). «О конструктивных функциях пространства Монте-Карло и результатах разделения для вероятностных классов сложности». Информация и вычисления . 75 (2): 178–189. doi : 10.1016/0890-5401(87)90057-5 .
Арора, Санджив; Боаз Барак (2009). «Вычислительная сложность: современный подход».

Внешние ссылки

Princeton CS 597E: Список статей по дерандомизации
Harvard CS 225: Псевдослучайность Архивировано 2003-08-05 на Wayback Machine