ПП (сложность)
-
Определение и свойства PP
- PP — это класс вероятностных алгоритмов, которые работают за полиномиальное время и выдают «ДА» с вероятностью, близкой к 1/2.
- Алгоритм PP может быть использован для решения задач, которые не могут быть решены за полиномиальное время с абсолютной уверенностью.
- PP включает в себя BPP, NP, MA, BQP, QMA и другие важные классы сложности.
-
Примеры и доказательства
- Пример PP-алгоритма: алгоритм, который выбирает случайное назначение переменных и проверяет, удовлетворяет ли оно формуле F.
- Теорема Тоды: PP включает в себя PH, всю полиномиальную иерархию, что свидетельствует о сложности решения задач в PP.
-
Полные задачи и замкнутость
- MAJSAT — пример полной задачи в PP.
- PP замкнут относительно дополнения, что означает, что для любого языка в PP существует его дополнение, также находящееся в PP.
-
Эквивалентные классы сложности
- PostBQP — класс квантовой сложности, эквивалентный PP.
- PQP — класс квантовой сложности, аналогичный BQP, но с ограниченной ошибкой.
-
Рекомендации и ссылки
- Статья содержит ссылки на «Зоопарк сложности: PP» и другие внешние ресурсы.
Полный текст статьи: