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

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

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

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

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

Определение

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

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

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

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

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

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

На практике вероятность ошибки 1/3 может быть неприемлема, однако выбор 1/3 в определении произволен. Изменение определения для использования любой константы от 0 до 1/2 (исключительно) вместо 1/3 не изменит результирующий набор BPP . Например, если определить класс с ограничением, что алгоритм может ошибаться с вероятностью не более 1/2. ¹⁰⁰, это приведет к тому же классу проблем. Вероятность ошибки даже не обязательно должна быть постоянной: тот же класс задач определяется допусканием ошибки до 1/2 − n. ^{− с} с одной стороны, или требующие погрешности всего 2 ^{− п ^с} с другой стороны, где 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 _путь . ^[3] BPP _путьИзвестно, что содержит NP и содержится в его квантовом аналоге PostBQP .

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

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

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

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

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

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

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

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

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

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

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

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

Лемма . Учитывая проблему (в частности, машинный код оракула и ограничение по времени) в релятивизированном $E НАПРИМЕР$ , для каждого частично построенного оракула и ввода длины n вывод можно зафиксировать, указав 2 ^{На )} ответы оракула.

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

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

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

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

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

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

{\textsf {i.o.-SUBEXP}}=\bigcap \nolimits _{\varepsilon >0}{\textsf {i.o.-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 ^{Ом ( п )} тогда Р = БПП . ^[10]

См. также

Ссылки

^ Валентин Кабанец, CMPT 710 - Теория сложности: Лекция 16 , 28 октября 2003 г.
^ Мадху Судан и Шиен Джин Онг. Массачусетский технологический институт: 6.841/18.405J Расширенная теория сложности: Лекция 6: Рандомизированные алгоритмы, свойства BPP . 26 февраля 2003 г.
^ «Зоопарк сложности:B — Зоопарк сложности» .
^ Лэнс Фортноу, Вытягивание квантовости , 20 декабря 2005 г.
^ Адлеман, LM (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), «О релятивизированных классах экспоненциальной и вероятностной сложности», Information and Control , 71 (3): 231–243, doi : 10.1016/S0019-9958(86)80012-2
^ Гольдрейх, Одед (2011). «В мире P = BPP» (PDF) . В Гольдрайхе, Одед (ред.). Исследования сложности и криптографии. Разное о взаимодействии случайности и вычислений - в сотрудничестве с Лидором Авигадом, Михиром Белларе, Звикой Бракерски, Шафи Гольдвассером, Шаем Халеви, Тали Кауфман, Леонидом Левином, Ноамом Нисаном, Даной Роном, Мадху Суданом, Лукой Тревизаном, Салилом Вадханом, Ави Вигдерсоном , Дэвид Цукерман . Конспекты лекций по информатике. Том. 6650. Спрингер. стр. 191–232. дои : 10.1007/978-3-642-22670-0_20 .
^ Бабай, Ласло; Пока, Лэнс; Нисан, Ноам; Вигдерсон, Ави (1993). « BPP имеет субэкспоненциальное моделирование времени, если у EXPTIME нет опубликованных доказательств». Вычислительная сложность . 3 (4): 307–318. дои : 10.1007/bf01275486 . S2CID 14802332 .
^ Рассел Импальяццо и Ави Вигдерсон (1997). « P = BPP, если E требует экспоненциальных схем: дерандомизация леммы XOR». Труды двадцать девятого ежегодного симпозиума ACM по теории вычислений , стр. 220–229. дои : 10.1145/258533.258590

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

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

[1] Валентин Кабанец, CMPT 710 - Теория сложности: Лекция 16 , 28 октября 2003 г.

[2] Мадху Судан и Шиен Джин Онг. Массачусетский технологический институт: 6.841/18.405J Расширенная теория сложности: Лекция 6: Рандомизированные алгоритмы, свойства BPP . 26 февраля 2003 г.

[3] «Зоопарк сложности:B — Зоопарк сложности» .

[4] Лэнс Фортноу, Вытягивание квантовости , 20 декабря 2005 г.

[5] Адлеман, LM (1978). «Две теоремы о случайном полиномиальном времени». Труды девятнадцатого ежегодного симпозиума IEEE по основам вычислительной техники . стр. 75–83.

[6] Беннетт, Чарльз Х .; Гилл, Джон (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

[7] Хеллер, Ганс (1986), «О релятивизированных классах экспоненциальной и вероятностной сложности», Information and Control , 71 (3): 231–243, doi : 10.1016/S0019-9958(86)80012-2

[8] Гольдрейх, Одед (2011). «В мире P = BPP» (PDF) . В Гольдрайхе, Одед (ред.). Исследования сложности и криптографии. Разное о взаимодействии случайности и вычислений - в сотрудничестве с Лидором Авигадом, Михиром Белларе, Звикой Бракерски, Шафи Гольдвассером, Шаем Халеви, Тали Кауфман, Леонидом Левином, Ноамом Нисаном, Даной Роном, Мадху Суданом, Лукой Тревизаном, Салилом Вадханом, Ави Вигдерсоном , Дэвид Цукерман . Конспекты лекций по информатике. Том. 6650. Спрингер. стр. 191–232. дои : 10.1007/978-3-642-22670-0_20 .

[Babai-9] Бабай, Ласло; Пока, Лэнс; Нисан, Ноам; Вигдерсон, Ави (1993). « BPP имеет субэкспоненциальное моделирование времени, если у EXPTIME нет опубликованных доказательств». Вычислительная сложность . 3 (4): 307–318. дои : 10.1007/bf01275486 . S2CID 14802332 .

[10] Рассел Импальяццо и Ави Вигдерсон (1997). « P = BPP, если E требует экспоненциальных схем: дерандомизация леммы XOR». Труды двадцать девятого ежегодного симпозиума ACM по теории вычислений , стр. 220–229. дои : 10.1145/258533.258590

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

v т и Классы сложности
Считается возможным	ВРЕМЯ ДЛОГА переменного тока ⁰ АСС ⁰ ТК ⁰ л СЛ РЛ Флорида Нидерланды NL-полный Северная Каролина СК СС П P-полный ЗПП РП БПП Министерство национальной обороны АПХ ФП
Подозрение неосуществимое	ВВЕРХ НАПРИМЕР NP-полный NP-жесткий со-НП со-NP-полный ТФНП ФНП ЯВЛЯЮСЬ КМА PH ⊕P ПП #П #P-полное ИП PSPACE PSPACE-полный
Считается невозможным	ВРЕМЯ ЭКСПРЕСС СЛЕДУЮЩЕЕ ВРЕМЯ EXPSPACE 2-ВРЕМЯ ЭКСПЛУАТАЦИИ ЭЛЕМЕНТАРНЫЙ пиар Р РЭ ВСЕ
Иерархии классов	Полиномиальная иерархия Экспоненциальная иерархия Иерарх Гжегорчик Арифметическая иерархия Булева иерархия
Семьи классов	DTIME NTIME ДСПЕЙС НСПАСЕ Вероятностно проверяемое доказательство Интерактивная система доказательств
Список классов сложности