Сложность вычислений
Probabilistically Checkable Proofs
В 1994 году исследователи доказали нечто парадоксальное: чтобы проверить NP-доказательство длиной в миллион битов, достаточно прочитать ровно три случайных бита. Не три тысячи, не три процента - ровно три бита. Эта теорема мгновенно сделала неаппроксимируемыми десятки оптимизационных задач, которые раньше казались просто «трудными».
- **Маршрутизация и TSP:** задача коммивояжёра не имеет полиномиальной аппроксимации лучше некоторых констант - PCP-теорема объясняет почему улучшать алгоритмы выше определённого порога бессмысленно.
- **Задачи планирования (scheduling):** для многих NP-трудных задач планирования жадные алгоритмы достигают PCP-границы - это означает, что инвестировать в более сложные алгоритмы теоретически бесполезно.
- **Верификация Zero-Knowledge доказательств:** идея PCP лежит в основе современных zkSNARK-систем, где краткое доказательство проверяется сэмплированием нескольких позиций.
PCP-теорема
В 1971 году Кук доказал NP-полноту SAT: любое NP-доказательство можно проверить детерминированно за полиномиальное время. Но детерминированная проверка требует читать всё доказательство целиком. В 1992 году Arora, Lund, Motwani, Sudan и Szegedy доказали нечто поразительное: каждое NP-доказательство можно перекодировать так, что верификатор с доступом к **O(log n) случайным битам** проверяет его корректность, читая лишь **O(1) позиций** в строке доказательства.
**PCP-теорема (1998, финальная форма):** NP = PCP(log n, 1). Для каждого языка L ∈ NP существует вероятностный верификатор V, который использует r = O(log n) случайных битов, читает q = O(1) битов из доказательства π, и при этом: если x ∈ L, то ∃π: Pr[V принимает] = 1; если x ∉ L, то ∀π: Pr[V принимает] ≤ 1/2.
Интуиция за теоремой: NP-доказательство переводится в избыточное кодирование (линейный код над GF(2)), где любое ошибочное доказательство «ломается» в большой доле позиций. Случайная проверка трёх позиций попадёт в сломанное место с константной вероятностью.
| Класс | Случайные биты | Запросы | Содержит |
|---|---|---|---|
| P | 0 | poly(n) | L ∈ P |
| NP (классика) | 0 | poly(n) | L ∈ NP |
| PCP(log n, 1) | O(log n) | O(1) | = NP (теорема) |
| PCP(poly n, 1) | poly(n) | O(1) | ⊇ PSPACE |
Верификатор в PCP(log n, 1) читает O(1) битов из доказательства. Сколько случайных битов он использует для выбора позиций?
Gap Amplification
PCP-теорема эквивалентна следующему утверждению о 3-SAT: существует полиномиальная редукция, которая переводит произвольную формулу φ в формулу φ' такую, что если φ выполнима - φ' тоже выполнима; если φ невыполнима - не более (1 - ε) доля клозов φ' одновременно выполнима для некоторой константы ε > 0. Это и есть **gap amplification** - усиление зазора между выполнимыми и невыполнимыми случаями.
Техника усиления зазора в доказательстве PCP-теоремы (Dinur, 2007 - упрощённое доказательство): берут граф ограничений задачи и повторно применяют два шага - **expander powering** (возведение в степень через экспандер, увеличивает зазор) и **alphabet reduction** (уменьшение алфавита обратно до константы). После O(log n) итераций зазор достигает константы.
**Алфавит vs зазор:** после каждого powering-шага алфавит растёт, но зазор тоже растёт. Alphabet reduction (через кодирование с малой ошибкой) возвращает алфавит к константе, сохраняя зазор. Этот баланс - ключевая идея доказательства Динура.
После применения gap amplification к невыполнимой формуле φ, формула φ' удовлетворяет условию: не более δ доли клозов выполнимо одновременно. Что происходит с размером φ'?
Inapproximability результаты
Из PCP-теоремы напрямую следует: **Max-3-SAT не аппроксимируем с коэффициентом > 7/8 при P ≠ NP**. Число 7/8 не случайно - именно столько клозов удовлетворяет случайное присваивание переменных (каждый 3-клоз неудовлетворён с вероятностью 1/8). Таким образом, простейший рандомизированный алгоритм оптимален по гарантии!
| Задача | Граница аппроксимации | Достигается |
|---|---|---|
| Max-3-SAT | 7/8 (PCP) | случайное присваивание |
| Vertex Cover | 2 - ε (UGC) | простой жадный |
| Clique | n^(1-ε) (Hastad) | нет poly-алгоритма |
| Set Cover | ln n (Feige) | жадный оптимален |
| Max-Cut | 0.878 (SDP, GW) | алгоритм Гёманса-Вильямсона |
Схема получения inapproximability результата: берут задачу L ∈ NP, применяют PCP-редукцию к задаче оптимизации (например, Max-CSP), затем показывают, что любой алгоритм с коэффициентом > c решал бы L за полиномиальное время. Константа c определяется параметрами PCP-верификатора.
Алгоритм случайного присваивания переменных для Max-3-SAT даёт гарантию 7/8. Что из этого следует в контексте PCP-теоремы?
Жёсткость аппроксимации на практике
PCP-результаты объясняют, почему многие LP/SDP-релаксации являются «правильными» алгоритмами: они достигают теоретического предела. Алгоритм Гёманса-Вильямсона (1995) для Max-Cut с коэффициентом 0.878 оптимален при Уникальной Гипотезе Игр (Unique Games Conjecture, Khot 2002). Если UGC верна - задача Vertex Cover не аппроксимируема лучше 2 - ε, хотя простой жадный даёт ровно 2.
**Уникальная Гипотеза Игр (UGC):** для любого ε > 0 NP-трудно отличить выполнимость системы линейных уравнений над Z_k (где каждое уравнение содержит ровно 2 переменных) с долей выполнимых ≥ 1-ε от случая с долей ≤ ε. UGC сильнее PCP и позволяет доказать оптимальность многих известных алгоритмов.
Самый практичный урок: перед разработкой алгоритма аппроксимации стоит проверить, есть ли известная нижняя граница. Если да - это потолок для любого полиномиального алгоритма. Если нет - возможно, задача допускает лучшую аппроксимацию или она NP-трудна для аппроксимации, просто граница ещё не доказана.
PCP-теорема доказывает, что задачи оптимизации не имеют приближённых алгоритмов вообще.
PCP-теорема устанавливает точные пороговые коэффициенты аппроксимации: алгоритмы с коэффициентом ниже порога существуют (и часто тривиальны), а с коэффициентом выше порога - недостижимы при P ≠ NP.
Разница принципиальна: Max-3-SAT имеет алгоритм с гарантией 7/8 (случайное присваивание), но не с 7/8 + ε. PCP говорит о границе, а не о полном запрете аппроксимации.
Алгоритм жадного покрытия множеств (Set Cover) даёт коэффициент аппроксимации ln(n). Что следует из результата Feige (1998) на основе PCP-теоремы?
Ключевые идеи
- **PCP-теорема:** NP = PCP(log n, 1) - каждое NP-доказательство можно перекодировать для проверки O(1) случайными запросами при O(log n) случайных битах.
- **Gap amplification:** PCP эквивалентна существованию полиномиальной редукции 3-SAT → Max-3-SAT с константным зазором между выполнимым (OPT=1) и невыполнимым (OPT ≤ 7/8) случаями.
- **7/8-граница для Max-3-SAT:** аппроксимация выше 7/8 невозможна при P ≠ NP; случайное присваивание достигает этой границы точно.
- **UGC расширяет результаты:** Уникальная Гипотеза Игр позволяет доказать оптимальность SDP-алгоритмов (Max-Cut 0.878, Vertex Cover 2) - многие жадные решения оказываются теоретически непревзойдёнными.
Связанные темы
PCP-теорема связывает несколько ключевых разделов теории вычислений:
- Рандомизированные алгоритмы — PCP-верификатор использует случайность; повторение уменьшает ошибку экспоненциально
- Интерактивные доказательства (IP, AM) — PCP - нерекурсивный аналог IP: нет взаимодействия, но есть доступ к всему доказательству случайно
Вопросы для размышления
- Если PCP-верификатор читает лишь 3 бита, как редко закодированное доказательство всё же содержит всю информацию об исходном доказательстве?
- Граница 7/8 для Max-3-SAT совпадает с вероятностью удовлетворения клоза случайным присваиванием. Случайность ли это, или за этим стоит более глубокая закономерность?
- Если бы P = NP было доказано, какая часть результатов об inapproximability автоматически рухнула бы, а какая осталась бы в силе?