ПП (сложность)
Алгоритм ПП
Отвечать
произведено
Правильный
ответ
ДаНет
Да> 1/2< 1/2
Нет< 1/2> 1/2
Класс задач по информатике
Диаграмма рандомизированных классов сложности
PP по отношению к другим вероятностным классам сложности ( ZPP , RP , co-RP, BPP , BQP ), которые обобщают P в пределах PSPACE . Неизвестно, являются ли какие-либо из этих включений строгими.

В теории сложности PP или PPT — это класс задач принятия решений , решаемых вероятностной машиной Тьюринга за полиномиальное время с вероятностью ошибки менее 1/2 для всех случаев. Аббревиатура PP относится к вероятностному полиномиальному времени. Класс сложности был определен Гиллом в 1977 году. [1]

Если задача принятия решения находится в PP , то для нее существует алгоритм, которому разрешено подбрасывать монеты и принимать случайные решения. Он гарантированно будет работать за полиномиальное время. Если ответ ДА, алгоритм ответит ДА с вероятностью больше 1/2. Если ответ НЕТ, алгоритм ответит ДА с вероятностью меньше 1/2. В более практическом смысле это класс задач, которые можно решить с любой фиксированной степенью точности, запустив рандомизированный алгоритм с полиномиальным временем достаточное (но ограниченное) количество раз.

Полиномиально-связанные и вероятностные машины Тьюринга характеризуются как PPT , что означает вероятностные полиномиальные машины. [2] Эта характеристика машин Тьюринга не требует ограниченной вероятности ошибки. Следовательно, PP — это класс сложности, содержащий все задачи, решаемые машиной PPT с вероятностью ошибки менее 1/2.

Альтернативная характеристика PP — это набор задач, которые могут быть решены недетерминированной машиной Тьюринга за полиномиальное время, где условием принятия является то, что большинство (более половины) путей вычисления принимает. Из-за этого некоторые авторы предложили альтернативное название Majority-P . [3]

Определение

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

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

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

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

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

В обоих определениях «меньше чем» можно изменить на «меньше или равно» (см. ниже), а порог 1/2 можно заменить любым фиксированным рациональным числом в диапазоне (0,1) без изменения класса.

ПП против БПП

BPP является подмножеством PP ; его можно рассматривать как подмножество, для которого существуют эффективные вероятностные алгоритмы. Различие заключается в допустимой вероятности ошибки: в BPP алгоритм должен давать правильный ответ (ДА или НЕТ) с вероятностью, превышающей некоторую фиксированную константу c > 1/2, например 2/3 или 501/1000. Если это так, то мы можем запустить алгоритм несколько раз и получить большинство голосов, чтобы достичь любой желаемой вероятности правильности меньше 1, используя границу Чернова . Это число повторений увеличивается, если c становится ближе к 1/2, но оно не зависит от размера входных данных n .

В более общем случае, если c может зависеть от размера входных данных полиномиально, как , то мы можем перезапустить алгоритм для и получить большинство голосов. По неравенству Хёффдинга это дает нам алгоритм BPP . н {\displaystyle n} с = О ( н − к ) {\displaystyle с=O(n^{-k})} О ( н 2 к ) {\displaystyle O(n^{2k})}

Важно то, что эта константа c не может зависеть от ввода. С другой стороны, алгоритму PP разрешено делать что-то вроде следующего:

  • В случае ДА выведите ДА с вероятностью 1/2 + 1/2 n , где n — длина входных данных.
  • В случае НЕТ выведите ДА с вероятностью 1/2 − 1/2 n .

Поскольку эти две вероятности экспоненциально близки друг к другу, даже если мы запустим его полиномиальное число раз, очень сложно сказать, работаем ли мы над экземпляром ДА или над экземпляром НЕТ. Попытка достичь фиксированного желаемого уровня вероятности с помощью большинства голосов и границы Чернова требует числа повторений, которое экспоненциально по n .

PP по сравнению с другими классами сложности

PP включает BPP , поскольку вероятностные алгоритмы, описанные в определении BPP, образуют подмножество алгоритмов в определении PP .

PP также включает NP . Чтобы доказать это, мы покажем, что проблема NP-полной выполнимости принадлежит PP . Рассмотрим вероятностный алгоритм, который, учитывая формулу F ( x 1 ,  x 2 , ...,  x n ), выбирает назначение x 1 ,  x 2 , ...,  x n равномерно случайным образом. Затем алгоритм проверяет, делает ли назначение формулу F истинной. Если да, он выводит YES. В противном случае он выводит YES с вероятностью и NO с вероятностью . 1 2 − 1 2 н + 1 {\displaystyle {\frac {1}{2}}-{\frac {1}{2^{n+1}}}} 1 2 + 1 2 н + 1 {\displaystyle {\frac {1}{2}}+{\frac {1}{2^{n+1}}}}

Если формула невыполнима, алгоритм всегда выведет YES с вероятностью . Если существует удовлетворяющее назначение, он выведет YES с вероятностью не менее (ровно 1/2, если он выбрал неудовлетворяющее назначение, и 1, если он выбрал удовлетворяющее назначение, в среднем до некоторого числа, большего 1/2). Таким образом, этот алгоритм помещает выполнимость в PP . Поскольку SAT является NP-полным, и мы можем префиксировать любое детерминированное сокращение полиномиального времени многих единиц в алгоритм PP , NP включен в PP . Поскольку PP замкнут относительно дополнения, он также включает co-NP . 1 2 − 1 2 н + 1 < 1 2 {\displaystyle {\frac {1}{2}}-{\frac {1}{2^{n+1}}}<{\frac {1}{2}}} ( 1 2 − 1 2 н + 1 ) ⋅ ( 1 − 1 2 н ) + 1 ⋅ 1 2 н = 1 2 + 1 2 2 н + 1 > 1 2 {\displaystyle \left({\frac {1}{2}}-{\frac {1}{2^{n+1}}}\right)\cdot \left(1-{\frac {1}{2^{n}}}\right)+1\cdot {\frac {1}{2^{n}}}={\frac {1}{2}}+{\frac {1}{2^{2n+1}}}>{\frac {1}{2}}}

Кроме того, PP включает MA , [4] , который включает в себя два предыдущих включения.

PP также включает BQP , класс задач принятия решений, решаемых эффективными квантовыми компьютерами с полиномиальным временем . Фактически, BQP низок для PP , что означает, что машина PP не получает никакой выгоды от возможности мгновенно решать задачи BQP . Класс полиномиального времени на квантовых компьютерах с постселекцией , PostBQP , равен PP [5] (см. #PostBQP ниже).

Кроме того, PP включает QMA , который включает в себя включения MA и BQP .

Полиномиальная машина Тьюринга с оракулом PP ( P PP ) может решить все проблемы в PH , всю полиномиальную иерархию . Этот результат был показан Сейносукэ Тодой в 1989 году и известен как теорема Тоды . Это доказательство того, насколько сложно решать проблемы в PP . Класс #P в некотором смысле примерно такой же сложный, поскольку P #P = P PP и, следовательно, P #P также включает PH . [6]

PP строго включает в себя равномерный TC 0 , класс булевых схем постоянной глубины с неограниченным вентилем по входу с мажоритарными вентилями , которые являются равномерными (генерируются алгоритмом с полиномиальным временем). [7]

PP включен в PSPACE . Это можно легко показать, представив алгоритм полиномиального пространства для MAJSAT , определенный ниже; просто попробуйте все назначения и подсчитайте количество удовлетворяющих.

По теореме Каннана PP не входит в SIZE (n k ) ни для какого k .

Полные проблемы и другие свойства

В отличие от BPP , PP является синтаксическим , а не семантическим классом. Любая полиномиально-временная вероятностная машина распознает некоторый язык в PP . Напротив, имея описание полиномиально-временной вероятностной машины, в общем случае невозможно определить, распознает ли она язык в BPP .

PP имеет естественные полные задачи, например, MAJSAT . [1] MAJSAT — это задача принятия решений, в которой дана булева формула F. Ответ должен быть ДА, если более половины всех назначений x 1 ,  x 2 , ...,  x n делают F истинным, и НЕТ в противном случае.

Доказательство того, что PP замкнуто относительно дополнения

Пусть L — язык в PP . Пусть обозначает дополнение L. По определению PP существует вероятностный алгоритм A с полиномиальным временем выполнения , обладающий тем свойством, что Л с {\displaystyle L^{c}}

х ∈ Л ⇒ Пр [ А  принимает  х ] > 1 2 и х ∉ Л ⇒ Пр [ А  принимает  х ] ≤ 1 2 . {\displaystyle x\in L\Rightarrow \Pr[A{\text{ принимает }}x]>{\frac {1}{2}}\quad {\text{и}}\quad x\not \in L\Rightarrow \Pr[A{\text{ принимает }}x]\leq {\frac {1}{2}}.}

Мы утверждаем, что без потери общности последнее неравенство всегда строгое; теорема может быть выведена из этого утверждения: пусть обозначает машину, которая является такой же, как A, за исключением того, что принимает, когда A отвергает, и наоборот. Тогда А с {\displaystyle А^{с}} А с {\displaystyle А^{с}}

х ∈ Л с ⇒ Пр [ А с  принимает  х ] > 1 2 и х ∉ Л с ⇒ Пр [ А с  принимает  х ] < 1 2 , {\displaystyle x\in L^{c}\Rightarrow \Pr[A^{c}{\text{ принимает }}x]>{\frac {1}{2}}\quad {\text{и}}\quad x\not \in L^{c}\Rightarrow \Pr[A^{c}{\text{ принимает }}x]<{\frac {1}{2}},}

что подразумевает, что находится в PP . Л с {\displaystyle L^{c}}

Теперь мы обосновываем наше предположение без потери общности. Пусть будет полиномиальной верхней границей времени выполнения A на входе x . Таким образом, A делает максимум случайных подбрасываний монеты во время своего выполнения. В частности, вероятность принятия является целым кратным и мы имеем: ф ( | х | ) {\displaystyle f(|x|)} ф ( | х | ) {\displaystyle f(|x|)} 2 − ф ( | х | ) {\displaystyle 2^{-f(|x|)}}

х ∈ Л ⇒ Пр [ А  принимает  х ] ≥ 1 2 + 1 2 ф ( | х | ) . {\displaystyle x\in L\Rightarrow \Pr[A{\text{ принимает }}x]\geq {\frac {1}{2}}+{\frac {1}{2^{f(|x|)}}}.}

Определите машину A ′ следующим образом: на входе x , A ′ запускает A как подпрограмму и отклоняет, если A отклонит; в противном случае, если A примет, A ′ подбрасывает монеты и отклоняет, если все они орлы, и принимает в противном случае. Тогда ф ( | х | ) + 1 {\displaystyle f(|x|)+1}

х ∉ Л ⇒ Пр [ А ′  принимает  х ] ≤ 1 2 ⋅ ( 1 − 1 2 ф ( | х | ) + 1 ) < 1 2 {\displaystyle x\not \in L\Rightarrow \Pr[A'{\text{ принимает }}x]\leq {\frac {1}{2}}\cdot \left(1-{\frac {1}{2^{f(|x|)+1}}}\right)<{\frac {1}{2}}}

и

х ∈ Л ⇒ Пр [ А ′  принимает  х ] ≥ ( 1 2 + 1 2 ф ( | х | ) ) ⋅ ( 1 − 1 2 ф ( | х | ) + 1 ) > 1 2 . {\displaystyle x\in L\Rightarrow \Pr[A'{\text{ принимает }}x]\geq \left({\frac {1}{2}}+{\frac {1}{2^{f(|x|)}}}\right)\cdot \left(1-{\frac {1}{2^{f(|x|)+1}}}\right)>{\frac {1}{2}}.}

Это оправдывает предположение (поскольку A ′ по-прежнему является вероятностным алгоритмом с полиномиальным временем) и завершает доказательство.

Дэвид Руссо доказал в своей докторской диссертации 1985 года [8] , что PP замкнуто относительно симметричной разности . В течение 14 лет оставался открытым вопрос о том, замкнуто ли PP относительно объединения и пересечения ; этот вопрос был решен утвердительно Бейгелем, Рейнгольдом и Шпильманом. [9] Альтернативные доказательства были позже даны Ли [10] и Ааронсоном (см. #PostBQP ниже).

Другие эквивалентные классы сложности

ПостBQP

Класс квантовой сложности BQP — это класс задач, решаемых за полиномиальное время на квантовой машине Тьюринга . Добавляя постселекцию , получаем более крупный класс, называемый PostBQP . Неформально постселекция дает компьютеру следующую силу: всякий раз, когда некоторое событие (например, измерение кубита в определенном состоянии) имеет ненулевую вероятность, вам разрешено предполагать, что оно имеет место. [11] Скотт Ааронсон показал в 2004 году, что PostBQP равен PP . [5] [12] Такая переформулировка PP упрощает демонстрацию определенных результатов, таких как то, что PP замкнуто относительно пересечения (и, следовательно, относительно объединения), что BQP является низким для PP и что QMA включено в PP .

ПКП

PP также равен другому классу квантовой сложности, известному как PQP , который является аналогом BQP с неограниченной ошибкой . Он обозначает класс задач принятия решений, решаемых квантовым компьютером за полиномиальное время, с вероятностью ошибки менее 1/2 для всех случаев. Даже если все амплитуды, используемые для вычисления PQP , взяты из алгебраических чисел, PQP все равно совпадает с PP . [13]

Примечания

  1. ^ ab Gill, John (1977). «Вычислительная сложность вероятностных машин Тьюринга». SIAM Journal on Computing . 6 (4): 675– 695. doi :10.1137/0206049.
  2. ^ Линделл, Йехуда; Кац, Джонатан (2015). Введение в современную криптографию (2-е изд.). Chapman and Hall/CRC. стр. 46. ISBN 978-1-4665-7027-6.
  3. ^ Лэнс Фортнау. Сложность вычислений: среда, 4 сентября 2002 г.: Класс сложности недели: PP. http://weblog.fortnow.com/2002/09/complexity-class-of-week-pp.html
  4. ^ Н.К. Верещагин, «О силе ПП»
  5. ^ ab Ааронсон, Скотт (2005). «Квантовые вычисления, постселекция и вероятностное полиномиальное время». Труды Королевского общества A. 461 ( 2063): 3473– 3482. arXiv : quant-ph/0412187 . Bibcode : 2005RSPSA.461.3473A. doi : 10.1098/rspa.2005.1546. S2CID  1770389.
  6. ^ Тода, Сейносукэ (1991). «PP так же сложна, как и иерархия полиномиального времени». SIAM Journal on Computing . 20 (5): 865– 877. doi :10.1137/0220053. MR  1115655.
  7. ^ Allender 1996, цитируется в Burtschick 1999
  8. ^ Дэвид Руссо (1985). Структурные свойства классов сложности (диссертация на степень доктора философии). Калифорнийский университет, Санта-Барбара.
  9. ^ Р. Бейгель, Н. Рейнгольд и Д. А. Шпильман, «PP замкнуто относительно пересечения», Труды симпозиума ACM по теории вычислений 1991 г. , стр. 1–9, 1991.
  10. ^ Лидэ Ли (1993). О счетных функциях (диссертация на степень доктора философии). Чикагский университет.
  11. ^ Ааронсон, Скотт. "Удивительная сила постселекции" . Получено 27 июля 2009 г.
  12. ^ Ааронсон, Скотт (2004-01-11). "Класс сложности недели: PP". Веблог Computational Complexity . Получено 2008-05-02 .
  13. ^ Ямаками, Томоюки (1999). «Анализ квантовых функций». Int. J. Found. Comput. Sci . 14 (5): 815– 852. arXiv : quant-ph/9909012 . Bibcode :1999quant.ph..9012Y. doi :10.1142/S0129054103002047. S2CID  3265603.

Ссылки

  • Пападимитриу, К. (1994). "глава 11". Вычислительная сложность . Эддисон-Уэсли..
  • Аллендер, Э. (1996). "Заметка о нижних границах равномерных схем для иерархии подсчета". Труды 2-й Международной конференции по вычислениям и комбинаторике (COCOON) . Заметки лекций по информатике. Том 1090. Springer-Verlag. С.  127–135 ..
  • Burtschick, Hans-Jörg; Vollmer, Heribert (1998). «Квантификаторы Линдстрема и определимость листового языка». Int. J. Found. Comput. Sci . 9 (3): 277– 294. doi :10.1142/S0129054198000180. ECCC  TR96-005.
Взято с "https://en.wikipedia.org/w/index.php?title=PP_(complexity)&oldid=1272915988"