Введение
Алгоритм PP > 1/2 < 1/2 < 1/2 > 1/2 Класс задач в информатике
Class of problems in computer science
In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time. The complexity class was defined by Gill in 1977. If a decision problem is in PP, then there is an algorithm for it that is allowed to flip coins and make random decisions. It is guaranteed to run in polynomial time. If the answer is YES, the algorithm will answer YES with probability more than 1/2. If the answer is NO, the algorithm will answer YES with probability less than 1/2. In more practical terms, it is the class of problems that can be solved to any fixed degree of accuracy by running a randomized, polynomial time algorithm a sufficient (but bounded) number of times. Turing machines that are polynomially bound and probabilistic are characterized as PPT, which stands for probabilistic polynomial time machines. This characterization of Turing machines does not require a bounded error probability. Hence, PP is the complexity class containing all problems solvable by a PPT machine with an error probability of less than 1/2. An alternative characterization of PP is the set of problems that can be solved by a nondeterministic Turing machine in polynomial time where the acceptance condition is that a majority (more than half) of computation paths accept. Because of this some authors have suggested the alternative name Majority P.
В теории сложности PP — это класс задач принятия, разрешимых вероятностной машиной Тьюринга за полиномиальное время, с вероятностью ошибки не превышающей 1/2 для всех экземпляров. Аббревиатура PP обозначает вероятностное полиномиальное время. Класс сложности был определён Гиллом в 1977 году. Если задача принятия принадлежит классу PP, то для неё существует алгоритм, которому разрешено подбрасывать монеты и принимать случайные решения. Гарантируется, что он выполнится за полиномиальное время. Если ответ "да", алгоритм ответит "да" с вероятностью более 1/2. Если ответ "нет", алгоритм ответит "да" с вероятностью менее 1/2. В более практическом смысле, это класс задач, которые можно решить с любой фиксированной степенью точности, многократно выполняя рандомизированный алгоритм за полиномиальное время достаточное (но ограниченное) число раз. Машины Тьюринга, ограниченные полиномиально и использующие вероятности, характеризуются как PPT (probabilistic polynomial time machines), то есть вероятностные машины полиномиального времени. Эта характеристика машин Тьюринга не требует ограниченной вероятности ошибки. Следовательно, PP — это класс сложности, содержащий все задачи, разрешимые машиной PPT с вероятностью ошибки не превышающей 1/2. Альтернативная характеристика PP — это множество задач, которые могут быть решены недетерминированной машиной Тьюринга за полиномиальное время, при этом условием принятия является то, что большинство (более половины) вычислительных путей приводят к принятию. В связи с этим некоторые авторы предложили альтернативное название Majority P.
Class of problems in computer science
In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time. The complexity class was defined by Gill in 1977. If a decision problem is in PP, then there is an algorithm for it that is allowed to flip coins and make random decisions. It is guaranteed to run in polynomial time. If the answer is YES, the algorithm will answer YES with probability more than 1/2. If the answer is NO, the algorithm will answer YES with probability less than 1/2. In more practical terms, it is the class of problems that can be solved to any fixed degree of accuracy by running a randomized, polynomial time algorithm a sufficient (but bounded) number of times. Turing machines that are polynomially bound and probabilistic are characterized as PPT, which stands for probabilistic polynomial time machines. This characterization of Turing machines does not require a bounded error probability. Hence, PP is the complexity class containing all problems solvable by a PPT machine with an error probability of less than 1/2. An alternative characterization of PP is the set of problems that can be solved by a nondeterministic Turing machine in polynomial time where the acceptance condition is that a majority (more than half) of computation paths accept. Because of this some authors have suggested the alternative name Majority P.
PP против BPP
BPP является подмножеством PP; его можно рассматривать как подмножество, для которого существуют эффективные вероятностные алгоритмы. Различие заключается в допустимой вероятности ошибки: в BPP алгоритм должен давать правильный ответ (ДА или НЕТ) с вероятностью, превышающей некоторую фиксированную константу c > 1/2, например, 2/3 или 501/1000. Если это так, то мы можем запустить алгоритм несколько раз и принять решение большинством голосов, чтобы достичь любой желаемой вероятности правильности, меньшей 1, используя границу Черноффа. Число повторений увеличивается, если c приближается к 1/2, но не зависит от размера входных данных n. В более общем случае, если c может зависеть от размера входных данных полиномиально, как , то мы можем повторно запустить алгоритм раз и принять решение большинством голосов. По неравенству Хоффдинга это дает нам алгоритм BPP. Важно, чтобы эта константа c не зависела от входных данных. С другой стороны, алгоритму PP разрешено делать следующее: для экземпляра YES выдавать YES с вероятностью 1/2 + 1/2n, где n – длина входных данных, а для экземпляра NO выдавать YES с вероятностью 1/2 - 1/2n. Поскольку эти две вероятности экспоненциально близки друг к другу, даже если запустить алгоритм полиномиальное число раз, очень сложно определить, работаем ли мы с экземпляром YES или NO. Попытка достичь фиксированного желаемого уровня вероятности с помощью большинства голосов и границы Черноффа требует числа повторений, экспоненциально зависящего от n.
More generally, if c can depend on the input size polynomially, as , then we can rerun the algorithm for and take the majority vote. By Hoeffding's inequality, this gives us a BPP algorithm. The important thing is that this constant c is not allowed to depend on the input. On the other hand, a PP algorithm is permitted to do something like the following:
On a YES instance, output YES with probability 1/2 + 1/2n, where n is the length of the input. On a NO instance, output YES with probability 1/2 − 1/2n. Because these two probabilities are exponentially close together, even if we run it for a polynomial number of times it is very difficult to tell whether we are operating on a YES instance or a NO instance. Attempting to achieve a fixed desired probability level using a majority vote and the Chernoff bound requires a number of repetitions that is exponential in n.
PP по сравнению с другими классами сложности
PP включает BPP, поскольку вероятностные алгоритмы, описанные в определении BPP, образуют подмножество алгоритмов, описанных в определении PP. PP также включает NP. Чтобы доказать это, мы покажем, что NP-полная задача выполнимости формулы принадлежит PP. Рассмотрим вероятностный алгоритм, который, получив формулу F(x1, x2, ..., xn), выбирает присваивание значений x1, x2, ..., xn равномерно случайным образом. Затем алгоритм проверяет, делает ли это присваивание формулу F истинной. Если да, то алгоритм выдает "ДА". В противном случае он выдает "ДА" с вероятностью ε и "НЕТ" с вероятностью 1-ε. Если формула невыполнима, алгоритм всегда выдает "ДА" с вероятностью 1. Если существует хотя бы одно выполнимое присваивание, он выдает "ДА" с вероятностью не менее 1/2 (точно 1/2, если выбрано невыполнимое присваивание, и 1, если выбрано выполнимое присваивание, в среднем – число больше 1/2). Таким образом, этот алгоритм помещает задачу выполнимости в класс PP. Поскольку SAT является NP-полной, и мы можем присоединить любое детерминированное полиномиальное преобразование к алгоритму PP, NP включается в PP. Поскольку PP замкнут относительно дополнения, он также включает co NP. Кроме того, PP включает MA, что охватывает два предыдущих включения. PP также включает BQP, класс задач принятия решений, разрешимых эффективными квантовыми компьютерами за полиномиальное время. Фактически, BQP является низким для PP, что означает, что машина PP не получает никакой выгоды от возможности мгновенно решать задачи BQP. Класс полиномиального времени на квантовых компьютерах с постселекцией, PostBQP, равен PP (см. #PostBQP ниже). Кроме того, PP включает QMA, что охватывает включения MA и BQP. Полиномиальная машина Тьюринга с оракулом PP (PPP) может решать все задачи в PH, всей полиномиальной иерархии. Этот результат был получен Сеиносуке Тодой в 1989 году и известен как теорема Тоды. Это свидетельствует о сложности решения задач в PP. Класс #P в некотором смысле столь же сложен, поскольку P#P = PPP и, следовательно, P#P также включает PH. PP строго включает унифицированный TC0, класс схем с постоянной глубиной, неограниченным веером и логическими элементами большинства, которые являются унифицированными (генерируемыми алгоритмом за полиномиальное время). PP включается в PSPACE. Это можно легко показать, представив алгоритм, использующий полиномиальное пространство, для MAJSAT, определенного ниже: просто перебрать все присваивания и подсчитать количество выполнимых. PP не включается в SIZE(nk) для любого k (доказательство).
If the formula is unsatisfiable, the algorithm will always output YES with probability If there exists a satisfying assignment, it will output YES with probability at least
(exactly 1/2 if it picked an unsatisfying assignment and 1 if it picked a satisfying assignment, averaging to some number greater than 1/2). Thus, this algorithm puts satisfiability in PP. As SAT is NP complete, and we can prefix any deterministic polynomial time many one reduction onto the PP algorithm, NP is included in PP. Because PP is closed under complement, it also includes co NP. Furthermore, PP includes MA, which subsumes the previous two inclusions. PP also includes BQP, the class of decision problems solvable by efficient polynomial time quantum computers. In fact, BQP is low for PP, meaning that a PP machine achieves no benefit from being able to solve BQP problems instantly. The class of polynomial time on quantum computers with postselection, PostBQP, is equal to PP (see #PostBQP below). Furthermore, PP includes QMA, which subsumes inclusions of MA and BQP. A polynomial time Turing machine with a PP oracle (PPP) can solve all problems in PH, the entire polynomial hierarchy. This result was shown by Seinosuke Toda in 1989 and is known as Toda's theorem. This is evidence of how hard it is to solve problems in PP. The class #P is in some sense about as hard, since P#P = PPP and therefore P#P includes PH as well. PP strictly includes uniform TC0, the class of constant depth, unbounded fan in boolean circuits with majority gates that are uniform (generated by a polynomial time algorithm). PP is included in PSPACE. This can be easily shown by exhibiting a polynomial space algorithm for MAJSAT, defined below; simply try all assignments and count the number of satisfying ones. PP is not included in SIZE(nk) for any k (proof).
Полные задачи и другие свойства
В отличие от BPP, PP является синтаксическим, а не семантическим классом. Любая вероятностная машина, работающая за полиномиальное время, распознает некоторый язык из PP. В отличие от этого, по описанию вероятностной машины, работающей за полиномиальное время, в общем случае неразрешимо определить, распознает ли она язык из BPP. Для PP существуют естественные полные задачи, например, MAJSAT. PP замкнута относительно симметрической разности. В течение 14 лет оставалось открытым вопросом, замкнута ли PP относительно объединения и пересечения; Beigel, Reingold и Spielman разрешили этот вопрос утвердительно. Li и Aaronson впоследствии предложили альтернативные доказательства (см. #PostBQP ниже).
ПослеBQP
Квантовый класс сложности BQP — это класс задач, разрешимых за полиномиальное время на квантовой машине Тьюринга. Добавление постселекции приводит к более широкому классу, называемому PostBQP. Неформально, постселекция наделяет компьютер следующей способностью: если какое-либо событие (например, измерение кубита в определенном состоянии) имеет ненулевую вероятность, допускается считать, что оно произошло. Скотт Ааронсон доказал в 2004 году, что PostBQP равен PP. Эта переформулировка PP упрощает доказательство определенных результатов, таких как замкнутость PP относительно пересечения (и, следовательно, относительно объединения), то, что BQP является низким для PP, и включение QMA в PP.
ПКП
PP также равен другому классу квантовой сложности, известному как PQP, который является аналогом BQP с допустимой любой ошибкой. Он обозначает класс задач принятия решений, разрешимых квантовым компьютером за полиномиальное время с вероятностью ошибки не превышающей 1/2 для всех экземпляров. Даже если все амплитуды, используемые в вычислениях PQP, берутся из алгебраических чисел, PQP всё равно совпадает с PP.