Формальные языки
Сведения (Reductions)
1971 год. Кук доказывает: SAT NP-полна. 1972 год. Карп публикует список из 21 NP-полной задачи через сведения. Один инструмент - polynomial-time reduction - связал тысячи задач в одну эквивалентную сеть. Сегодня более 3000 задач доказаны NP-полными через цепочки сведений. Сведение - универсальный язык теории сложности.
- **Cook-Levin теорема:** SAT NP-полна - первое доказательство NP-полноты. Кук сводил произвольную НМТ к формуле пропозициональной логики. SAT-солверы (Z3, MiniSAT) используются в верификации схем Intel, планировании, биоинформатике
- **AWS Lambda планировщик:** задача оптимального размещения Lambda-функций на серверах - bin packing (NP-complete). AWS использует аппроксимационные алгоритмы вместо точного решения
- **Компилятор: register allocation:** задача распределения регистров - graph coloring (NP-complete). LLVM использует жадные эвристики (greedy coloring) вместо оптимального решения за приемлемое время
- **Маршрутизация пакетов:** оптимальная маршрутизация в сети - NP-hard вариант TSP. Интернет использует аппроксимирующие протоколы (OSPF, BGP) с эвристическими метриками
Mapping reduction (many-one reduction)
**Mapping reduction** A ≤m B: существует вычислимая функция f такая, что для всех w: w ∈ A ⟺ f(w) ∈ B. Если решить B - можно решить A: вычислить f(w), спросить у алгоритма для B. Если A неразрешима и A ≤m B - B тоже неразрешима. Это стандартный метод доказательства неразрешимости.
**Логика сведения:** A ≤m B означает «B сложнее или равна A». Если A неразрешима и A ≤m B, то B не легче A - значит B тоже неразрешима. Контрапозитив: если B разрешима и A ≤m B, то A разрешима. Сведения выстраиваются в цепочки: A ≤m B ≤m C - транзитивность. Если A неразрешима, то C тоже.
Для mapping reduction A ≤m B нужна функция f. Какие условия на f?
Turing reduction (oracle reduction)
**Turing reduction** A ≤T B: существует МТ с оракулом B, решающая A. Оракул отвечает на вопросы «x ∈ B?» за один шаг. Turing reduction мощнее mapping reduction: если A ≤m B, то A ≤T B, но не наоборот. Turing reduction позволяет задавать множественные запросы к оракулу и использовать их ответы.
На практике в теории вычислимости чаще используется **mapping reduction** - она проще и её достаточно для большинства доказательств неразрешимости. В теории сложности polynomial-time Turing reduction (≤pT) используется для определения **NP-hardness**: задача X NP-hard если для любого Y ∈ NP: Y ≤pT X.
A ≤m B (mapping reduction). Что можно сказать о Turing reduction?
Примеры сведений
Рассмотрим цепочку сведений для доказательства неразрешимости задачи E_TM = {<M> : L(M) = ∅}. Идея: если бы E_TM был разрешим, можно было бы решить A_TM. Сведение работает через конструирование вспомогательной МТ.
| Задача | Статус RE | Доказательство |
|---|---|---|
| A_TM = {<M,w>: M принимает w} | RE, не Decidable | Распознаватель: запустить M. Неразрешима: диагонализация |
| HALT = {<M,w>: M останавливается} | RE, не Decidable | A_TM <=_m HALT |
| E_TM = {<M>: L(M)=empty} | co-RE, не RE | A_TM <=_m co-E_TM |
| EQ_TM = {<M1,M2>: L(M1)=L(M2)} | Ни RE ни co-RE | E_TM <=_m EQ_TM и co-E_TM <=_m EQ_TM |
| REGULAR_TM = {<M>: L(M) рег.} | Ни RE ни co-RE | Теорема Райса |
В сведении A_TM к E_TM строится машина M_w, которая игнорирует свой вход. Зачем?
Polynomial-time reductions и NP-полнота
Та же концепция сведения работает в теории сложности. **Polynomial-time mapping reduction** A ≤pₘ B: вычислимая за poly(n) функция f такая, что w ∈ A ⟺ f(w) ∈ B. Если B разрешима за poly(n) и A ≤pₘ B, то A разрешима за poly(n). Язык B **NP-hard** если для всех A ∈ NP: A ≤pₘ B.
Красота теории NP-полноты: **все NP-полные задачи сводятся друг к другу** за полиномиальное время. Если найти poly-алгоритм для одной - получить poly-алгоритм для всех. SAT, 3-SAT, Vertex Cover, Clique, Hamiltonian Path, TSP (decision version) - все они эквивалентны с точностью до полиномиального множителя.
Сведение (reduction) означает упрощение: задача A сводится к более простой задаче B
A ≤ B означает 'B не легче A' - A сводится к B, значит B умеет решать всё что A. Если A сложная - B тоже не может быть проще
В математике 'A сводится к B' читается как 'для решения A достаточно уметь решать B'. Если A неразрешима и A ≤ B, то B тоже должна быть достаточно сложной (неразрешимой). Направление сведения противоположно интуиции: A ≤ B означает B >= A по сложности.
3-SAT ≤pₘ Vertex Cover - polynomial-time reduction. Если найти poly-алгоритм для Vertex Cover, что следует?
Ключевые идеи
- **Mapping reduction A ≤m B:** вычислимая функция f: w ∈ A ⟺ f(w) ∈ B. A неразрешима + A ≤m B => B неразрешима
- **Turing reduction A ≤T B:** МТ с оракулом B решает A. Мощнее mapping, но сложнее доказывать. Mapping => Turing (не наоборот)
- **Цепочки сведений:** A ≤m B ≤m C - транзитивность. Неразрешимость распространяется через цепочку
- **Poly-time reduction A ≤pₘ B:** та же концепция для теории сложности. Основа определения NP-полноты и доказательств NP-hard через сведения
Связанные темы
Сведения - универсальный инструмент теории вычислимости и сложности:
- Проблема остановки — HALT - базовая неразрешимая задача; большинство других неразрешимостей доказывается сведением от HALT
- NP-полнота — NP-полнота определяется через poly-time reductions от SAT; тот же механизм что mapping reduction
- Теорема Райса — Доказывается сведением от A_TM: показывает, что все нетривиальные свойства программ неразрешимы
Вопросы для размышления
- Сведение A ≤m B означает 'A не сложнее B'. Почему интуиция может подсказывать обратное - что 'A сводится к B' значит 'A проще'?
- В теории NP-полноты все задачи сводятся друг к другу. Означает ли это, что они одинаково трудны на практике (с одинаковыми константами)?
- LLVM использует жадный алгоритм для выделения регистров (NP-hard задача). Как оценить качество такого приближения?