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

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

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

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

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

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

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

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

• M работает за полиномиальное время на всех входах
• Для всех х в L , М выходов 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) без изменения класса.

PP против BPP [ править ]

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

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

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

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

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

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

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

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

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

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

PP не содержится в SIZE (n ^k ) для любого k ( доказательство ).

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

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

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

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

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

${\displaystyle 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, за исключением того, что принимает, когда A отвергает, и наоборот. потом ${\displaystyle A^{c}}$${\displaystyle A^{c}}$

${\displaystyle 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}},}$

откуда следует, что находится в пп .${\displaystyle L^{c}}$

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

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

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

${\displaystyle 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 г. тезис ^[6] о замкнутости ПП относительно симметричной разности . Это была открытой проблема 14 лет ли ПП была закрыта при объединении и пересечении ; это было утвердительно установлено Бейгелем, Рейнгольдом и Шпильманом. ^[7] Альтернативные доказательства были позже даны Ли ^[8] и Ааронсоном (см. #PostBQP ниже).

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

PostBQP [ править ]

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

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 . Cite journal requires |journal= (help).

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

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