Что такое классы P и NP, NP-полные задачи и что с ними делать на практике?

P — задачи, решаемые за полиномиальное время; NP — задачи, где предложенное решение можно проверить за полином; NP-полные — самые трудные в NP: полиномиальный алгоритм для любой из них дал бы его для всех.

Определения

• P ⊆ NP: если умеем решать быстро, то и проверить быстро. Равенство P = NP — открытая проблема.
• NP-трудная задача: к ней полиномиально сводится любая задача из NP. Она не обязана лежать в NP — например, проблема остановки.
• NP-полная = NP-трудная и принадлежит NP. Первая — SAT (теорема Кука–Левина).
• NP-полноту доказывают так: проверка решения за полином плюс сведение уже известной NP-полной задачи к нашей (не наоборот).
• Классика: 3-SAT, вершинное покрытие, клика, гамильтонов цикл, раскраска в 3 цвета, subset sum, TSP и рюкзак в версии «да/нет».

Похожие, но простые

Эйлеров цикл — O(V + E), а гамильтонов — NP-полный. 2-SAT решается за линейное время, 3-SAT — NP-полная. Кратчайший путь — P, самый длинный простой путь — NP-трудный.

Что делать на практике

• Малый n — точный экспоненциальный алгоритм: TSP динамикой по подмножествам за O(n²·2ⁿ) тянет n ≈ 20.
• Псевдополиномиальное решение: рюкзак за O(n·W) при небольшом W.
• Приближённые алгоритмы с гарантией: вершинное покрытие — 2-приближение, метрический TSP — 1.5 (Кристофидес).
• Эвристики и локальный поиск: жадность, 2-opt, имитация отжига.
• Готовые SAT/ILP/CP-солверы (OR-Tools CP-SAT, Gurobi) — на реальных входах они часто справляются с миллионами переменных.

Коротко для собеседования

NP-полноту задачи стоит распознать быстро: это сигнал не искать точный полиномиальный алгоритм. Дальше выбирают по ограничениям — точный перебор или ДП при малом n, приближения и эвристики для больших входов, готовые SAT/ILP-солверы для реальных задач.