Класс 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 — это длина входа.
• Если правильный ответ «Нет», алгоритм говорит «Да» с вероятностью 1/2-1/2ⁿ.

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

Классы сложности алгоритмов

 

Cчитаются лёгкими	P • L • NL • AC • NC • P-complete • BQP • BPP • RP • ZPP
Предпологаются сложными	NP (co-NP • NP-complete • co-NP-complete ) • UP • #P (#P-complete ) • IP • PSPACE (PSPACE-complete) • R • PP • AM
Cчитаются сложными	EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-complete • Co-RE-complete • PH
Список алгоритмов

Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.