Класс PP

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

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

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.