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

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

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

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

Определение [ править ]

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

• M работает за полиномиальное время на всех входах
• Для всех х в L , М выходов 1 с вероятностью , большей чем или равной ² / ₃
• Для всех й не в L , М выходы 1 с вероятностью меньше или равны ¹ / ₃

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

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

• M работает за полиномиальное время на всех входах
• Для всех х в L , доля строк у длины р (| х |) , которые удовлетворяют условию , что больше , чем или равным ² / ₃${\ Displaystyle М (х, у) = 1}$
• Для всех й не в L , фракции строк у длины р (| х |) , которые удовлетворяют условие меньше или равно ¹ / ₃${\ Displaystyle М (х, у) = 1}$

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

На практике вероятность ошибки ¹ / ₃ не может быть приемлемой, однако, выбор ¹ / ₃ в определении является произвольным. Это может быть любой константа между 0 и ¹ / ₂ (Exclusive) и множеством БППЫ будут неизменными. Он даже не должен быть постоянным: тот же класс проблем определяются позволяя ошибку так высоко , как ¹ / ₂ - п ^{- с} , с одной стороны, или требующей ошибку как малые , как 2 ^{- н гр} , с другой стороны, где c - любая положительная постоянная, а nдлина ввода. Идея состоит в том, что существует вероятность ошибки, но если алгоритм запускается много раз, вероятность того, что большинство запусков ошибочны, падает экспоненциально из-за границы Чернова . ^[1] Это позволяет создать высокоточный алгоритм, просто запустив алгоритм несколько раз и получив «большинство голосов» за ответы. Например, если один определенный класс с тем ограничением , что алгоритм может быть неправильно с вероятностью не более ¹ / _{2 ¹⁰⁰} , это привело бы к тому же классу проблем.

Проблемы [ править ]

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

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

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

Связанные классы [ править ]

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

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

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

Свойства теории сложности [ править ]

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

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

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

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

Свойства закрытия [ править ]

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

Релятивизация [ править ]

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

Существует даже оракул, в котором BPP = EXP ^NP (и, следовательно, 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 линейного времени достаточно, даже для функциональных задач (если задан функциональный оракул и линейный выходной размер) и с экспоненциально малой (с линейной экспонентой) вероятностью ошибки. Кроме того , эта конструкция является эффективным в том , что задано произвольное оракула А мы можем организовать оракула B , чтобы иметь P ^A ≤P ^B и EXP ^{NP A} = EXP ^{NP B} = BPP ^B . Также для ЗПП= EXP oracle (и, следовательно, ZPP = BPP = EXP <NEXP), можно было бы исправить ответы в релятивизированном вычислении E на специальный неответ, таким образом гарантируя, что не будет дано ложных ответов.

Дерандомизация [ править ]

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

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

${\displaystyle {\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 , где

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

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

См. Также [ править ]

• RP
• ЗПП
• BQP
• Список классов сложности

Ссылки [ править ]

• Валентин Кабанец (2003). «CMPT 710 - Теория сложности: Лекция 16». Университет Саймона Фрейзера .
• Христос Пападимитриу (1993). Вычислительная сложность (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). «Случайность, доказуемость и разделение времени и пространства Монте-Карло». Конспект лекций по информатике . 270 : 189–207.
• Карпинский, Марек ; Вербеек, Рутгер (1987b). «О конструктивных функциях пространства Монте-Карло и результатах разделения для классов вероятностной сложности». Информация и вычисления . 75 (2): 178–189. DOI : 10.1016 / 0890-5401 (87) 90057-5 .
• Арора, Санджив; Вооз Барак (2009). «Вычислительная сложность: современный подход».

Внешние ссылки [ править ]

• Princeton CS 597E: список документов по дерандомизации
• Harvard CS 225: Псевдослучайность