Кратко и по существу.
Что такое формальный язык и проблема разрешимости
- Формальный язык — это множество слов над конечным алфавитом ${\Sigma }^{\ast }$.
- Задача принятия решения (decision problem) эквивалентна языку $L\subseteq {\Sigma }^{\ast }$: проверка, принадлежит ли вход $w$ языку $L$.
- Язык (задача) разрешим (decidable, рекурсивен), если существует алгоритм, который на любом входе останавливается и отвечает «да»/«нет». Полуразрешим (recursively enumerable, r.e.) — есть алгоритм, который останавливается и принимает все «да»-входы, на «нет»-входах может не останавливаться.
Классы сложности (основное)
- $\mathrm{P}$: задачи, решаемые за полиномиальное время $O(n^k)$.
- $\mathrm{NP}$: задачи, для «да»-ответа существует сертификат, проверяемый за полиномиальное время.
- $\mathrm{NP}$-полные: самые трудные задачи в $\mathrm{NP}$; если одна из них в $\mathrm{P}$, то $\mathrm{P}=\mathrm{NP}$. Обозначение свёртки: $A{\le }_{p}B$ — полиномиально сводится.
Примеры задач
- Примеры в $\mathrm{P}$:
- Проверка связности неориентированного графа: BFS/DFS за время $O(n+m)$ ($n$ — число вершин, $m$ — рёбер).
- Одноисточниковые кратчайшие пути с неотрицательными весами: Дейкстра за $O(m+n\log n)$.
- Поиск остовного дерева (Kruskal/Prim) — полиномиально.
- Проверка принадлежности слова регулярному языку (DFA) — линейно по длине слова.
- Тест простоты числа (AKS) — полиномиальное время.
- Примеры в $\mathrm{NP}$ (и часто частые примеры):
- SAT (булева выполнимость): для данного формулы существует ли удовлетворяющее присваивание — если дать присваивание, его проверяют за полиномиальное время.
- Hamiltonian Path: существует ли гамильтонов путь в графе — сертификат: порядок вершин.
- Subset Sum (решение задачи о сумме подмножества) — сертификат: подмножество.
- Примеры $\mathrm{NP}$-полных:
- 3-SAT (Кук—Левин: SAT является $\mathrm{NP}$-полной).
- CLIQUE, VERTEX COVER, HAMILTONIAN CYCLE, 0/1 KNAPSACK (в варианте решения — сильно/слабо NP-полный), TSP (решение: существует ли цикл длины $\le k$).
- Связь: 3-SAT ${\le }_p$ CLIQUE и т.д.
- Неразрешимые (undecidable) задачи:
- Проблема остановки: $HALT=\{⟨M,x⟩\mid M\text{останавливается на}x\}$ — неразрешима, но полуразрешима.
- Общая удовлетворимость формул первого порядка (Entscheidungsproblem) — неразрешима.
- Post Correspondence Problem (PCP) — неразрешима.
- По Риса: любое нетривиальное семантическое свойство программ (о языке, которые они принимают/выдают) неразрешимо.
Практическое значение классификаций для разработки алгоритмов
- Если задача в $\mathrm{P}$: ожидается эффективный (масштабируемый) алгоритм; цель — оптимизация констант и простых степеней полинома. Приоритет — точные решения и инженерная оптимизация.
- Если задача $\mathrm{NP}$-полна: маловероятно существование полиномиального алгоритма (при предположении $\mathrm{P}\ne \mathrm{NP}$). Практические стратегии:
- искать приближённые (approximation) алгоритмы с гарантиями качества;
- использовать эвристики, локальный поиск, метаэвристики или SAT/ILP-солверы для реальных входов;
- изучать специальные случаи/ограничения входа, которые попадают в $\mathrm{P}$ или FPT (параметризованная сложность);
- использовать точные экспоненциальные алгоритмы с улучшенной базой (например $O(2^{n/2})$ и т. п.), если входы малы.
- Если задача полуразрешима (r.e.): можно применять «полуалгоритмы», которые останавливаются на «да»-ответах; для «нет»-ответов нужны допущения (ограничение времени/пространства) или доказательства отсутствия решения.
- Если задача неразрешима: нет общего алгоритма, дающего корректный ответ на всех входах. Практические подходы:
- ограничить язык или модель (декретировать decidable-подкласс);
- использовать приближённые/консервативные анализы (sound but incomplete);
- применять отсечённые/ограниченные по ресурсам процедуры (bounded model checking).
- Выводы для инженера:
- классификация дает ориентир: стоит ли искать точный полиномиальный алгоритм или лучше сразу переходить к приближению/эвристике;
- сводимости (${\le }_p$) позволяют переносить результаты: доказав, что новая задача $\mathrm{NP}$-полна, вы экономите время на поиске «лучшего» алгоритма;
- знание о неразрешимости указывает на необходимость смены формулировки задачи или ограничи- тельств модели.
Короткое резюме
- Формальные языки ↔ задачи принятия решений; разрешимость — существование алгоритма, который всегда останавливается.
- $\mathrm{P}$ — эффективно решаемые, $\mathrm{NP}$ — проверяемые сертификатом, $\mathrm{NP}$-полные — «наиболее трудные» в $\mathrm{NP}$.
- Неразрешимые — алгоритма вообще не существует; для них применяют ограничения, полуалгоритмы или приближения.
- Эти классификации направляют выбор методов при проектировании и оценке алгоритмов.