В теории сложности , ПП является класс задач принятия решений разрешимых с помощью вероятностной машины Тьюринга в полиномиальное время , с вероятностью ошибки менее 1/2 всех случаев. Аббревиатура PP относится к вероятностному полиномиальному времени. Класс сложности был определен [1] Гиллом в 1977 году.
Если проблема решения связана с PP , то для нее существует алгоритм, позволяющий подбрасывать монеты и принимать случайные решения. Гарантированно работает за полиномиальное время. Если ответ ДА, алгоритм ответит ДА с вероятностью более 1/2. Если ответ НЕТ, алгоритм ответит ДА с вероятностью, меньшей или равной 1/2. С практической точки зрения, это класс задач, которые можно решить с любой фиксированной степенью точности, запустив рандомизированный алгоритм с полиномиальным временем достаточное (но ограниченное) количество раз.
Машины Тьюринга, которые являются полиномиально связанными и вероятностными, характеризуются как PPT , что означает вероятностные машины с полиномиальным временем. [2] Эта характеристика машин Тьюринга не требует ограниченной вероятности ошибки. Следовательно, PP - это класс сложности, содержащий все задачи, решаемые машиной PPT с вероятностью ошибки менее 1/2.
Альтернативная характеристика PP - это набор проблем, которые могут быть решены недетерминированной машиной Тьюринга за полиномиальное время, где условием приемлемости является то, что большинство (более половины) путей вычисления принимают. По этой причине некоторые авторы предложили альтернативное название Majority-P . [3]
Язык L принадлежит PP тогда и только тогда, когда существует вероятностная машина Тьюринга M такая, что
В качестве альтернативы PP можно определить, используя только детерминированные машины Тьюринга. Язык L принадлежит PP тогда и только тогда, когда существует многочлен p и детерминированная машина Тьюринга M , такие что
В обоих определениях «меньше или равно» можно заменить на «меньше чем» (см. Ниже), а порог 1/2 может быть заменен любым фиксированным рациональным числом в (0,1) без изменения класса.
BPP - это подмножество PP ; его можно рассматривать как подмножество, для которого существуют эффективные вероятностные алгоритмы. Различие заключается в допустимой вероятности ошибки: в BPP алгоритм должен давать правильный ответ (ДА или НЕТ) с вероятностью, превышающей некоторую фиксированную константу c> 1/2, например 2/3 или 501/1000. Если это так, то мы можем запустить алгоритм несколько раз и получить большинство голосов для достижения любой желаемой вероятности правильности меньше 1, используя границу Чернова . Это количество повторов увеличивается, если c становится ближе к 1/2, но это не зависит от входного размера n .
Важно то, что эта константа c не может зависеть от ввода. С другой стороны, алгоритму PP разрешено делать что-то вроде следующего:
Поскольку эти две вероятности настолько близки друг к другу, особенно для больших n , даже если мы запускаем его большое количество раз, очень трудно определить, работаем ли мы с экземпляром YES или с экземпляром NO. Попытка достичь фиксированного желаемого уровня вероятности с использованием большинства голосов и границы Чернова требует числа повторений, которое является экспоненциальным по n .
PP включает BPP , поскольку вероятностные алгоритмы, описанные в определении BPP, образуют подмножество алгоритмов в определении PP .
PP также включает NP . Чтобы доказать это, мы показываем, что проблема NP-полной выполнимости принадлежит PP . Рассмотрим вероятностный алгоритм, который по формуле F ( x 1 , x 2 , ..., x n ) выбирает присвоение x 1 , x 2 , ..., x n равномерно случайным образом. Затем алгоритм проверяет, делает ли присвоение истинной формулу F. Если да, выводится ДА. В противном случае он выводит ДА с вероятностью и НЕТ с вероятностью .
Если формула невыполнима, алгоритм всегда с вероятностью выдаст ДА . Если существует удовлетворительное назначение, он будет выводить YES с вероятностью не менее (точно 1/2, если он выбрал неудовлетворительное назначение, и 1, если он выбрал удовлетворительное назначение, с усреднением до некоторого числа больше 1/2). Таким образом, этот алгоритм ставит выполнимость в пп . Поскольку SAT является NP-полным, и мы можем префикс любой детерминированной полиномиальной редукции "многие-один" в алгоритме PP , NP включается в PP . Поскольку PP закрывается при дополнении, он также включает co-NP .
Кроме того, ПП включает в себя 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 не входит в РАЗМЕР (n k ) для любого k ( доказательство ).
В отличие от BPP , PP - это синтаксический, а не семантический класс. Любая вероятностная машина с полиномиальным временем распознает некоторый язык в PP . Напротив, учитывая описание вероятностной машины с полиномиальным временем, в целом невозможно определить, распознает ли она язык в BPP .
У PP есть естественные законченные задачи, например MAJSAT . MAJSAT - это проблема принятия решений, в которой задается логическая формула F. Ответ должен быть ДА, если более половины всех присваиваний x 1 , x 2 , ..., x n делают F истинным, и НЕТ в противном случае.
Пусть L - язык в PP . Пусть обозначим дополнение L . По определению PP существует вероятностный алгоритм A с полиномиальным временем, обладающий тем свойством, что
Мы утверждаем, что без ограничения общности последнее неравенство всегда строго; теорема может быть выведена из этого утверждения: пусть обозначает машину, которая такая же, как A, за исключением того, что принимает, когда A отвергает, и наоборот. потом
откуда следует, что находится в пп .
Обоснуем наше без ограничения общности предположение. Позвольте быть полиномиальной верхней границей времени работы A на входе x . Таким образом, A совершает не более случайных подбрасываний монеты во время выполнения. В частности, вероятность принятия является целым числом, кратным, и мы имеем:
Определите машину A ′ следующим образом: на входе x , A ′ запускает A как подпрограмму и отклоняет, если A отклоняет; в противном случае, если A примет, A 'подбрасывает монеты и отклоняет их, если все они орел, и принимает в противном случае. потом
Это подтверждает предположение (поскольку A 'все еще является вероятностным алгоритмом с полиномиальным временем) и завершает доказательство.
Дэвид Руссо доказал в своей докторской диссертации 1985 г. тезис [6] о замкнутости ПП относительно симметричной разности . В течение 14 лет оставалось открытым вопрос о том, закрывается ли PP при объединении и пересечении ; это было положительно установлено Бейгелем, Рейнгольдом и Шпильманом. [7] Альтернативные доказательства были позже даны Ли [8] и Ааронсоном (см. #PostBQP ниже).
Класс квантовой сложности BQP - это класс задач, решаемых за полиномиальное время на квантовой машине Тьюринга . Добавляя поствыбор , получается более крупный класс PostBQP . Неформально пост-выбор дает компьютеру следующие возможности: всякий раз, когда какое-либо событие (например, измерение кубита в определенном состоянии) имеет ненулевую вероятность, вы можете предположить, что оно имеет место. [9] Скотт Ааронсон в 2004 году показал, что PostBQP равен PP . [5] [10] Эта переформулировка PP упрощает отображение определенных результатов, например, PPзамкнуто относительно пересечения (и, следовательно, относительно объединения), что BQP является низким для PP , и что QMA входит в PP .
PP также равен другому классу квантовой сложности, известному как PQP , который является аналогом неограниченной ошибки BQP . Он обозначает класс задач принятия решений, решаемых квантовым компьютером за полиномиальное время с вероятностью ошибки менее 1/2 для всех случаев. Даже если все амплитуды, используемые для вычисления PQP, взяты из алгебраических чисел, PQP все равно совпадает с PP . [11]
|journal=
( помощь ) .