NP-полные задачи

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

Зачем нужно

Знание теории NP-полноты помогает разработчику вовремя распознать задачи, для которых точное решение на практике недостижимо. Вместо бесплодного поиска «быстрого» алгоритма можно сразу перейти к аппроксимациям, эвристикам или специальным случаям. Это экономит время и предотвращает архитектурные просчёты.

Где используется

Оптимизация маршрутов (задача коммивояжёра, TSP) в логистике
Составление расписаний (SAT-планировщики)
Криптография: сложность взлома RSA основана на NP-трудных задачах
Компиляторы: оптимальное распределение регистров — NP-полная задача
Биоинформатика: выравнивание последовательностей ДНК

Основной контент

Иерархия классов сложности

P ⊆ NP ⊆ NP-hard
         NP-complete = NP ∩ NP-hard

P (Polynomial) — задачи, решаемые за полиномиальное время O(n^k).
NP (Nondeterministic Polynomial) — задачи, решение которых проверяется за полиномиальное время.
NP-hard — задачи, к которым сводится любая задача из NP; могут быть не в NP сами.
NP-complete — задачи одновременно в NP и NP-hard.

Главный открытый вопрос CS: P = NP? На практике считается P ≠ NP.

Метод сведения (reduction)

Задача A сводится к задаче B (A ≤_p B), если любой экземпляр A можно преобразовать в экземпляр B за полиномиальное время. Если B легко решить — A тоже легко.

Первая NP-полная задача — SAT (Boolean Satisfiability), доказана теоремой Кука–Левина (1971).

Классические NP-полные задачи

Задача	Краткое описание
SAT	Выполнима ли булева формула?
3-SAT	SAT с клаузами по 3 литерала
TSP (decision)	Есть ли тур короче K?
Knapsack (decision)	Можно ли набрать стоимость ≥ V при весе ≤ W?
Graph Coloring	Можно ли раскрасить граф в k цветов?
Clique	Есть ли клика размера k?
Vertex Cover	Есть ли покрытие вершинами размера ≤ k?
Hamiltonian Path	Есть ли путь, проходящий через каждую вершину ровно раз?

Стратегии работы с NP-полными задачами

# Стратегия 1: точное решение для малых n
# Knapsack через DP — O(n * W), псевдополиномиальное
def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(W + 1):
            dp[i][w] = dp[i-1][w]
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i-1][w - weights[i-1]] + values[i-1])
    return dp[n][W]

# Стратегия 2: жадная аппроксимация (нет гарантии оптимума)
# Стратегия 3: локальный поиск, симуляция отжига
# Стратегия 4: специальный случай (планарный граф, дерево)

Псевдополиномиальное vs полиномиальное

Knapsack решается за O(n·W), но W — число, а не длина входа. Если W экспоненциально велик — это не полиномиально. Такие алгоритмы называют псевдополиномиальными.

Частые ошибки

Путать NP с «неразрешимой» задачей. NP — не бесконечно сложно, а «проверяется быстро, решается неизвестно как быстро».
Считать, что NP-полная задача всегда требует экспоненциального времени — для фиксированных параметров (FPT) может быть полиномиальное решение.
Забывать про псевдополиномиальные алгоритмы: они практически применимы при ограниченных числовых значениях.
Пропускать аппроксимационные алгоритмы — для TSP существует (1 + ε)-аппроксимация на евклидовой плоскости.