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

Алгоритм ПП
Отвечать произведено Правильный отвечать	Да	Нет
Да	> 1/2	< 1/2
Нет	< 1/2	> 1/2

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

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

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

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

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

Определение

Язык 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.

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

ПП против БПП

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

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

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

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

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

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

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

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

Если формула невыполнима, алгоритм всегда с вероятностью выдаст ДА. ${\frac {1}{2}}-{\frac {1}{2^{n+1}}}<{\frac {1}{2}}$. Если существует удовлетворяющее присваивание, оно выдаст ДА с вероятностью не менее $\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 . Поскольку SAT является NP-полным, и мы можем префикс любого детерминированного полиномиального сокращения «много-единица» к алгоритму PP , NP включен в PP . Поскольку PP закрыт относительно дополнения, он также включает в себя со-NP .

Кроме того, ПП включает в себя МА , что включает в себя два предыдущих включения.

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

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

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

ПП строго включает единый ТК ⁰ , класс логических схем с неограниченным разветвлением постоянной глубины и однородными мажоритарными вентилями (генерируемыми алгоритмом с полиномиальным временем).

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

ПП не входит в РАЗМЕР (n ^к ) для любого k по теореме Каннана .

Полные задачи и другие свойства

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

У ПП естественно полные проблемы, например у MAJSAT . MAJSAT — это задача решения, в которой задана булева формула F. Ответ должен быть ДА, если более половины всех присваиваний x ₁ , x ₂ , ..., x _n делают F истинным, и НЕТ в противном случае.

Доказательство того, что PP закрыт при дополнении

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

$x\in L\Rightarrow \Pr[A{\text{ accepts }}x]>{\frac {1}{2}}\quad {\text{and}}\quad x\not \in L\Rightarrow \Pr[A{\text{ accepts }}x]\leq {\frac {1}{2}}.$

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

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

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

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

$x\in L\Rightarrow \Pr[A{\text{ accepts }}x]\geq {\frac {1}{2}}+{\frac {1}{2^{f(|x|)}}}.$

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

$x\not \in L\Rightarrow \Pr[A'{\text{ accepts }}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{ accepts }}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 году докторскую степень. диссертация что ПП замкнут относительно симметричной разности . оставался открытым вопрос о В течение 14 лет ли ПП том, закрыт при объединении и пересечении ; это было решено положительно Бейгелем, Рейнгольдом и Шпильманом. Альтернативные доказательства были позже даны Ли. и Ааронсон (см. #PostBQP ниже).

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

ПостBQP

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

ПКП

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

Ссылки

• Пападимитриу, К. (1994). «глава 11». Вычислительная сложность . Аддисон-Уэсли. .
• Аллендер, Э. (1996). «Заметка о нижних границах равномерной схемы для счетной иерархии». Материалы 2-й Международной конференции по вычислительной технике и комбинаторике (COCOON) . Конспекты лекций по информатике. Том. 1090. Шпрингер-Верлаг. стр. 127–135. .
• Бурчик, Ханс-Йорг; Воллмер, Гериберт (1998). «Кванторы Линдстрема и определимость листового языка». Межд. Дж. Нашел. Вычислить. Наука . 9 (3): 277–294. дои : 10.1142/S0129054198000180 . ЕССС   ТР96-005 .

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

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