Класс PP

Положение класса PP в иерархии классов сложности.

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

Определение

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

• M полиномиальна по времени
• Для любого x из L, M возвращает 1 с вероятностью строго большей 1/2
• Для любого x не из L, M возвращает 1 с вероятностью не большей 1/2

PP и BPP

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

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

• Если правильный ответ «Да», алгоритм говорит «Да» с вероятностью 1/2+1/2^n, где n — это длина входа.
• Если правильный ответ «Нет», алгоритм говорит «Да» с вероятностью 1/2-1/2^n.

Так как эти две возможности достаточно близки, в особенности для больших n, даже если машина Тьюринга будет запущена большое количество раз очень сложно понять, работаем ли мы с вариантом, где правильный ответ «Да» или «Нет». Попытка добиться фиксированного значения вероятности, используя большинство голосов, требует количество повторений, экспоненциальное по n. Грубо, это можно сравнить с задачей определения, какой стороной выпадет монетка с небольшим перевесом, подбрасывая её большое количество раз.