Класс PP

Материал из Википедии — свободной энциклопедии

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

[править] 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. Грубо, это можно сравнить с задачей определения, какой стороной выпадет монетка с небольшим перевесом, подбрасывая ее большое количество раз.

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