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

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

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

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

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

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

Определение

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

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

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

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

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

ПП против БПП

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

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

• В случае YES выведите YES с вероятностью 1/2 + 1/2.^п, где п - длина ввода.
• В случае NO выведите YES с вероятностью 1/2 - 1/2.^п.

Поскольку эти две вероятности так близки друг к другу, особенно для больших п, даже если мы запускаем его много раз, очень трудно определить, работаем ли мы с экземпляром YES или с экземпляром NO. Попытка достичь фиксированного желаемого уровня вероятности с использованием большинства голосов и границы Чернова требует числа повторений, которое является экспоненциальным по п.

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

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

PP также содержит НП. Чтобы доказать это, покажем, что НП-полный выполнимость проблема принадлежит PP. Рассмотрим вероятностный алгоритм, который по формуле F(Икс₁, Икс₂, ..., Икс_п) выбирает задание Икс₁, Икс₂, ..., Икс_п равномерно наугад. Затем алгоритм проверяет, делает ли присвоение формулу F правда. Если да, выводится ДА. В противном случае с вероятностью выдаст YES. ${ displaystyle { frac {1} {2}} - { frac {1} {2 ^ {n + 1}}}}$ и НЕТ с вероятностью ${ displaystyle { frac {1} {2}} + { frac {1} {2 ^ {n + 1}}}}$.

Если формула невыполнима, алгоритм всегда будет выдавать ДА с вероятностью ${ displaystyle { frac {1} {2}} - { frac {1} {2 ^ {n + 1}}} <{ frac {1} {2}}}$. Если существует удовлетворительное задание, оно выдаст YES с вероятностью не менее${ 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}}}$(ровно 1/2, если он выбрал неудовлетворительное задание, и 1, если он выбрал удовлетворительное задание, в среднем до некоторого числа больше 1/2). Таким образом, этот алгоритм ставит выполнимость в PP. Так как СИДЕЛ является NP-полным, и мы можем префикс любой детерминированной редукция "много-один" за полиномиальное время на PP алгоритм, НП содержится в PP. Потому что PP закрыто по дополнению, также содержит со-НП.

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

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

Более того, PP содержит QMA, который включает включения MA и BQP.

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

PP строго содержит TC⁰, класс однородной неограниченно-веерной постоянной глубины логические схемы с участием ворота большинства. (Allender 1996, цитируется по Burtschick 1999).

PP содержится в PSPACE. Это легко показать, продемонстрировав алгоритм в полиномиальном пространстве для МАДЖСАТ, определенный ниже; просто попробуйте все задания и посчитайте количество удовлетворительных.

PP не содержится в РАЗМЕР(п^k) для любого k (доказательство ).

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

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

PP имеет естественные полные проблемы, например, МАДЖСАТ. МАДЖСАТ - это проблема принятия решений, в которой задается логическая формула F. Ответ должен быть ДА, если более половины всех присваиваний Икс₁, Икс₂, ..., Икс_п сделайте F истинным и NO в противном случае.

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

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

${ displaystyle x in L Rightarrow Pr [A { text {принимает}} x]> { frac {1} {2}} quad { text {and}} quad x not in L Rightarrow Pr [A { text {принимает}} x] leq { frac {1} {2}}.}$

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

${ displaystyle x in L ^ {c} Rightarrow Pr [A ^ {c} { text {accept}} x]> { frac {1} {2}} quad { text {and}} quad x not in L ^ {c} Rightarrow Pr [A ^ {c} { text {accept}} x] <{ frac {1} {2}},}$

откуда следует, что ${ displaystyle L ^ {c}}$ в PP.

Обоснуем наше без ограничения общности предположение. Позволять ${ Displaystyle f (| х |)}$ - полиномиальная верхняя граница времени работы А на входе Икс. Таким образом А делает самое большее ${ Displaystyle f (| х |)}$ случайное подбрасывание монеты во время ее исполнения. В частности, вероятность принятия является целым числом, кратным ${ Displaystyle 2 ^ {- е (| х |)}}$ и у нас есть:

${ displaystyle x in L Rightarrow Pr [A { text {принимает}} x] geq { frac {1} {2}} + { frac {1} {2 ^ {f (| x | )}}}.}$

Определить машину А′ Следующим образом: на входе Икс, А'Бежит А как подпрограмму и отклоняет, если А отвергнет; в противном случае, если А принял бы, А'Сальто ${ Displaystyle f (| х |) +1}$ монеты и отклоняет, если все они орел, и принимает в противном случае. потом

${ 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}} quad { text {and}} quad 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}}.}$

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

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

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

PostBQP

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

PQP

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

Заметки

использованная литература

• Пападимитриу, К. (1994). «Глава 11». Вычислительная сложность. Эддисон-Уэсли..
• Аллендер, Э. (1996). «Заметка о нижних границах единой схемы для счетной иерархии». Труды 2-й Международной конференции по вычислительной и комбинаторике (COCOON). Конспект лекций по информатике. 1090. Springer-Verlag. С. 127–135..
• Burtschick, Hans-Jörg; Фоллмер, Хериберт (1999). «Квантификаторы Линдстрема и определяемость языка листьев». ECCC  TR96-005. Цитировать журнал требует | журнал = (Помогите).

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

• Зоопарк сложности: PP