Оглавление [Скрыть]
ПП (сложность)
-
Определение и свойства 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” и другие внешние ресурсы.
Полный текст статьи: