Сложность вычислений
Полиномиальная иерархия
Задача «существует ли схема с минимальным числом элементов, эквивалентная данной?» - не просто NP-трудна, она труднее любой задачи из NP. Такие задачи живут на втором этаже бесконечной башни классов над NP. Полиномиальная иерархия - это эта башня, и понять её структуру значит понять, насколько разные «степени недетерминизма» отличаются друг от друга.
- **Model checking и верификация:** проверка свойств типа «для всех сценариев ошибки существует восстановление» - естественная Π₂-задача, которая не сводится к NP без экспоненциального раздутия.
- **Криптографические security games:** безопасность схемы шифрования формулируется как: «для всех атакующих A существует симулятор S...» - чередование кванторов по роли агентов прямо соответствует уровням PH.
- **AI Planning с частичной наблюдаемостью:** классическое планирование ∈ PSPACE, но с k чередованиями наблюдаемости/скрытости оно попадает в Σₖ уровень PH.
Уровни Σ и Π полиномиальной иерархии
NP можно охарактеризовать через существование: L ∈ NP тогда и только тогда, когда существует полиномиально проверяемый сертификат. co-NP - через отрицание: L ∈ co-NP тогда и только тогда, когда для всех входов сертификат отсутствия полиномиально проверяем. Полиномиальная иерархия (PH) расширяет этот паттерн, чередуя кванторы ∃ и ∀.
Пример задачи из Σ₂: «Существует ли формула φ такая, что ни одна формула размера меньше |φ| не эквивалентна ей?» - нужно проверить существование φ (∃) и для всех φ' меньшего размера неэквивалентность (∀). Пример из Π₂: «Для всех k-раскрасок графа G хотя бы одно ребро монохроматично» - здесь ∀ идёт первым.
| Уровень | Тип квантора | Пример задачи | Содержит |
|---|---|---|---|
| Σ₁ = NP | ∃ | SAT, Clique, Hamilton | NP-полные |
| Π₁ = co-NP | ∀ | TAUTOLOGY, UNSAT | co-NP-полные |
| Σ₂ | ∃∀ | MIN-DNF, ΣₚP-complete | Σ₂-полные |
| Π₂ | ∀∃ | MAX-CLIQUE-SIZE≥k? | Π₂-полные |
| PSPACE | ∀∃∀∃... | QBF, TQBF | PH ⊆ PSPACE |
Задача: «Существует ли истинное присваивание x₁...xₙ такое, что для всех y₁...yₙ формула φ(x,y) ложна?» Какому уровню иерархии принадлежит эта задача?
Оракульные машины
Машина Тьюринга с **оракулом** O - это МТ с дополнительной лентой запросов: она записывает слово w на ленту запросов, переходит в состояние «запрос», и в следующем шаге получает ответ «да/нет» на вопрос «w ∈ O?» - за один шаг, независимо от сложности O. Класс NP^A обозначает задачи, решаемые за недетерминированное полиномиальное время с оракулом к языку A.
**Альтернативная теорема** (Chandra-Kozen-Stockmeyer): PH = APTIME = ATM с poly-time и O(1) чередованиями. Это даёт комбинаторную интуицию: каждый уровень иерархии - это игра с фиксированным числом ходов между двумя игроками (∃ и ∀).
Важное следствие: если SAT ∈ P (то есть P = NP), то PH схлопывается до P. Если NP = co-NP, то Σ₁ = Π₁, и PH схлопывается до Σ₁ = NP. Каждое коллапсирование иерархии было бы сенсационным открытием.
Машина P^NP (детерминированная полиномиальная с NP-оракулом) совпадает с классом Δ₂ = P^SAT. Какому уровню PH это соответствует?
Релятивизация и её ограничения
В 1975 году Baker, Gill и Solovay доказали теорему релятивизации: существуют оракулы A и B такие, что P^A = NP^A, и P^B ≠ NP^B. Это означает: **любое доказательство вопроса P vs NP, которое «релятивизируется» (работает для любого оракула), не может решить задачу**, так как для разных оракулов ответ разный.
**Что означает «релятивизируется»:** доказательство P = NP релятивизируется, если для любого оракула O оно доказывает P^O = NP^O. Диагонализация (метод времени-пространство компромисса, Space Hierarchy Theorem и т.д.) релятивизируется. Алгебраические методы (IP = PSPACE - Shamir 1992) не релятивизируются.
Из теоремы релятивизации следует, что для доказательства P ≠ NP потребуются **нерелятивизирующие** техники - методы, которые используют внутреннюю структуру вычислений, а не только их входы/выходы. Алгебраизация (Aaronson-Wigderson, 2009) показала, что даже алгебраические обобщения не достаточны: нужны принципиально новые методы.
Теорема Baker-Gill-Solovay показывает, что диагонализирующие доказательства не могут разрешить P vs NP. Почему теорема Шамира (IP = PSPACE) это обходит?
Теоремы о коллапсировании
Ключевое свойство PH: любое «неожиданное» совпадение уровней влечёт коллапс всей иерархии. Это делает PH структурно хрупкой: если хоть что-то схлопывается - рушится всё. Наиболее важные импликации:
Квантифицированные булевы формулы (QBF, TQBF) - это PSPACE-полная задача: «∃x₁ ∀x₂ ∃x₃ ... φ(x₁,...,xₙ) = 1?» с неограниченным числом кванторов. Она находится над PH: если PH = PSPACE, то PH = PSPACE и TQBF ∈ PH, что большинство исследователей считает маловероятным.
**Практическая значимость PH:** задачи из Σ₂ встречаются в верификации (model checking с кванторами), AI planning (частичная наблюдаемость создаёт уровни неопределённости), криптографии (security games с чередующимися ролями атакующего и защитника). Знание уровня задачи в PH даёт нижнюю оценку сложности.
Полиномиальная иерархия бесконечна - это доказанный факт.
Бесконечность PH - открытая проблема. Известно лишь, что если PH конечна (схлопывается к некоторому Σₖ), то это влечёт маловероятные следствия. Под предположением P ≠ NP иерархия, по всей видимости, бесконечна, но это не доказано.
Доказать бесконечность PH так же трудно, как разделить уровни иерархии - это потребует нерелятивизирующих техник, которых пока нет.
Предположим, доказано NP = co-NP. Что произойдёт с полиномиальной иерархией?
Ключевые идеи
- **PH строится кванторами:** Σₖ = ∃∀∃... (k кванторов), Πₖ = ∀∃∀... (k кванторов); Σ₁ = NP, Π₁ = co-NP, PH = объединение всех уровней.
- **Оракульная машина = уровень иерархии:** Σₖ = NP с оракулом к Σₖ₋₁; каждый уровень даёт машине доступ к предыдущему уровню за один шаг.
- **BGS-теорема запрещает диагонализацию:** существуют оракулы A, B с P^A = NP^A и P^B ≠ NP^B, поэтому диагонализирующие техники принципиально не могут разрешить P vs NP.
- **Коллапс хрупок:** NP = co-NP тянет PH → Σ₁ = NP; Σₖ = Πₖ для любого k тянет PH → Σₖ. Иерархия «ломается каскадом».
Связанные темы
Полиномиальная иерархия соединяет несколько фундаментальных понятий теории сложности:
- Интерактивные доказательства (IP) — IP = PSPACE; нерелятивизирующее доказательство, которое обходит BGS-барьер через алгебраизацию
- Пространственная иерархия — PH ⊆ PSPACE; Space Hierarchy Theorem доказывает бесконечность пространственной иерархии диагонализацией (что невозможно для PH)
Вопросы для размышления
- Если бы оказалось, что P = NP, вся полиномиальная иерархия схлопнулась бы до P. Что это говорит о природе «уровней сложности» - они реальны или являются артефактом нашего незнания?
- BGS-теорема показывает, что для разных оракулов ответ на P vs NP разный. Означает ли это, что сам вопрос P vs NP зависит от «контекста вычислений», или это свидетельство ограниченности метода диагонализации?
- Каждый уровень PH добавляет один квантор. В чём смысл «одного квантора» с точки зрения вычислительной мощности - что именно даёт переход от Σₖ к Σₖ₊₁?