Теория сложности: классы P, NP, PSPACE, редукции и полнота

Есть задачи, которые компьютер решить не может в принципе — про них говорит теория вычислимости. А есть задачи, которые он решить может, но за время, превышающее возраст Вселенной. Практически разницы между ними никакой, но математически это два разных мира, и второй куда богаче и ближе к работе инженера.

Теория сложности отвечает на вопрос: сколько ресурсов (времени, памяти, случайности, недетерминизма) принципиально нужно, чтобы решить задачу — не этим алгоритмом, а любым возможным алгоритмом. Это важное отличие от анализа алгоритмов. «Быстрая сортировка работает за O(n log n)» — утверждение об алгоритме. «Сортировка сравнениями требует Ω(n log n)» — утверждение о задаче, нижняя граница, которую не обойдёт никто и никогда. Теория сложности — про такие утверждения.

Практический выхлоп для программиста максимально конкретный. Когда вы доказали, что ваша задача NP-полна, вы перестали искать полиномиальный алгоритм и начали строить эвристику, аппроксимацию или SAT-кодировку — и сэкономили месяцы. Когда криптограф говорит «стойкость опирается на трудность факторизации», он делает утверждение из теории сложности. Когда планировщик запросов в PostgreSQL после 12 таблиц в JOIN переключается с динамического программирования на генетический алгоритм — это тоже теория сложности, только зашитая в исходники.

Статья опирается на логику и доказательства (кванторы, доказательство от противного), дискретную математику (асимптотика, счёт) и теорию графов (почти все канонические NP-полные задачи — про графы).

Четыре сцены из жизни

Сцена 1. Вас просят «просто оптимизировать». Продакт хочет, чтобы система строила оптимальные маршруты для 200 курьеров. Вы прикидываете и обнаруживаете, что это задача коммивояжёра с ограничениями. Правильный ответ не «сделаю за спринт» и не «это невозможно», а: «точный оптимум недостижим, дам решение в пределах 5% от оптимума за 30 секунд, и вот доказательство, что лучшего гарантированного качества за разумное время не существует».

Сцена 2. Регулярка вешает прод. (a+)+b на строке из 30 букв a съедает секунды. Причина — бэктрекинг-движок, чей худший случай экспоненциален. Это не баг реализации: сопоставление с обратными ссылками — NP-трудная задача, и никакая оптимизация её не спасёт. Спасает смена модели вычисления (детерминированный автомат, см. автоматы и языки).

Сцена 3. Менеджер пакетов «думает» пять минут. Разрешение зависимостей с версионными ограничениями — это буквально SAT. Современные менеджеры (libsolv в zypper/dnf, Dart pub, Cargo) внутри содержат SAT-решатель, а не жадный алгоритм. Осознание «моя задача — это SAT» даёт доступ ко всей индустрии решателей.

Сцена 4. Ваша криптосистема безопасна ровно настолько, насколько трудна одна задача. RSA стоит на факторизации, ECDSA — на дискретном логарифме. Если бы P = NP (в конструктивном варианте), рухнули бы обе. Стойкость — это утверждение о нижних границах, которые никто не умеет доказывать; мы работаем на вере, подкреплённой десятилетиями неудачных атак.

Общее у всех сцен: вопрос не «какой алгоритм написать», а «в какой класс попадает задача и что этот класс разрешает».

Что именно мы измеряем

Задача, экземпляр, кодировка

Определение (задача разрешения). Задача разрешения — это язык A ⊆ {0,1}*, то есть множество строк. «Решить задачу» = построить алгоритм, который для входа x отвечает x ∈ A? («да»/«нет»).

Почему только «да/нет», ведь нам нужен маршрут, а не факт его существования? Потому что теория так проще, а потеря невелика: почти всегда версия поиска сводится к версии разрешения за полиномиальное число вызовов (самосводимость, self-reducibility). Хотите найти выполняющий набор для формулы — спросите оракула «выполнима ли формула при x1 = true?», зафиксируйте ответ, повторите n раз. n вызовов — и у вас полный набор.

Кодировка имеет значение — но не так сильно, как кажется. Число 100 в двоичной записи занимает 7 бит, в унарной — 100. Алгоритм, полиномиальный от значения числа, но экспоненциальный от длины его записи, называют псевдополиномиальным. Классика — динамическое программирование для задачи о рюкзаке за O(n·W): выглядит полиномом, но W — это значение, а вход содержит log W бит. Отсюда правило: сложность всегда меряется от длины входа в битах, при «разумной» кодировке (двоичной для чисел, списком рёбер или матрицей смежности для графов — они полиномиально переводятся друг в друга).

Модель вычисления и почему она почти не важна

Формально время и память определяются на машине Тьюринга: время — число шагов, память — число посещённых ячеек рабочей ленты. Программисту это кажется абсурдной моделью — где массивы с произвольным доступом?

Спасает тезис о полиномиальной эквивалентности: все «разумные» детерминированные последовательные модели (одноленточная и многоленточная МТ, RAM-машина, ваш ноутбук, любой язык программирования) моделируют друг друга с полиномиальными накладными расходами. Многоленточная МТ моделируется одноленточной с квадратичным замедлением; RAM с логарифмической стоимостью — полиномиально. Значит свойство «решается за полином» не зависит от модели — и именно поэтому класс P является робастным математическим объектом, а не артефактом железа.

Что этот тезис ломает: квантовые компьютеры (класс BQP, факторизация за полином по алгоритму Шора) — известный кандидат в контрпримеры для «расширенного тезиса Чёрча–Тьюринга». Аналоговые/«бесконечно точные» модели ломают его тривиально и потому нечестны.

Худший случай, асимптотика и их честная критика

Классы определяются через худший случай и асимптотику. Оба выбора спорны, и важно понимать, что именно вы теряете:

Ответ теории на первую критику — сложность в среднем (Левин) и класс distNP; на вторую — «мелкозернистая сложность» (fine-grained complexity), где вместо «полином или нет» доказывают «нельзя быстрее n^(2-ε) при гипотезе SETH». Читать: Impagliazzo, «A Personal View of Average-Case Complexity» — https://cseweb.ucsd.edu/~russell/average.ps

Класс P: рабочее определение «эффективно»

Определение. P = ⋃_k DTIME(n^k) — множество языков, разрешимых детерминированной машиной Тьюринга за время O(n^k) для некоторого фиксированного k.

Почему именно полином — это тезис Кобхэма–Эдмондса (1965), эмпирическое соглашение, а не теорема. У него есть три сильных аргумента:

1. Замкнутость относительно композиции. Полином от полинома — полином. Значит можно свободно вызывать подпрограммы, оборачивать, сводить одно к другому, не выходя из класса. Ни O(n log n), ни 2^(log^2 n) таким свойством не обладают так удобно.
2. Независимость от модели (см. выше).
3. Эмпирика. Когда задача попадает в P, показатель степени почти всегда оказывается 2–4. Первый полиномиальный алгоритм редко бывает практичным, но за ним обычно следуют быстрые: линейное программирование (эллипсоидный метод Хачияна 1979 — полиномиален и медленен; методы внутренней точки — полиномиальны и быстры), проверка простоты (AKS 2002, https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf).

Контраргумент — «галактические алгоритмы»: полиномиальные алгоритмы с константами, делающими их бесполезными на любом мыслимом входе. Пример: следствия теоремы Робертсона–Сеймура дают O(n^3)-алгоритмы для проверки минорной характеристики, но с константой, зависящей от запрещённых миноров совершенно чудовищно. P — про принципиальную структурную границу, не про бенчмарк.

NP: две двери в одну комнату

Класс NP определяют двумя способами. Оба нужны: первый интуитивен и годится для доказательств принадлежности, второй — для теорем.

Определение через сертификат (проверяющий)

Определение. Язык A ∈ NP, если существует полиномиальный по времени детерминированный алгоритм V (верификатор) и полином p, такие что:

x ∈ A   ⟺   существует строка w с |w| ≤ p(|x|), для которой V(x, w) = «принять»

Строка w — сертификат (свидетель, доказательство). Читается по-человечески: NP — это задачи, у которых ответ «да» можно быстро проверить, если кто-то подсказал решение.

Заметьте асимметрию, зашитую в кванторы: «существует w» для ответа «да», но для «нет» требуется «для всех w» — а это уже не проверяется быстро. Эта асимметрия — источник всей структуры теории (см. co-NP ниже).

Проверим на живой задаче. SUBSET-SUM: даны числа и цель, есть ли подмножество с нужной суммой? Сертификат — список индексов; верификатор складывает и сравнивает.

import itertools

def verify_subset_sum(instance, certificate):
    """Верификатор для SUBSET-SUM. Работает за O(len(certificate)) — полином от входа."""
    nums, target = instance
    # сертификат обязан быть корректным по форме: индексы в диапазоне и без повторов
    if not set(certificate) <= set(range(len(nums))):
        return False
    if len(set(certificate)) != len(certificate):
        return False
    return sum(nums[i] for i in certificate) == target

def solve_subset_sum_bruteforce(instance):
    """Перебор всех сертификатов: 2^n вызовов верификатора.
    Это буквально «недетерминированная машина, симулируемая детерминированно»."""
    nums, _ = instance
    for r in range(len(nums) + 1):
        for cert in itertools.combinations(range(len(nums)), r):
            if verify_subset_sum(instance, cert):
                return cert
    return None

inst = ([3, 34, 4, 12, 5, 2], 9)
print(solve_subset_sum_bruteforce(inst))       # (2, 4)  ->  4 + 5 = 9
print(verify_subset_sum(inst, (0, 5, 2)))      # True    ->  3 + 2 + 4 = 9
print(verify_subset_sum(inst, (0, 0, 0)))      # False   ->  повтор индекса

Обратите внимание на структуру: проверка — полином, поиск — экспонента. Ровно это и есть вопрос P vs NP: обязательно ли поиск дороже проверки?

Определение через недетерминизм

Определение. NP = ⋃_k NTIME(n^k), где недетерминированная МТ на каждом шаге может «разветвиться» и принимает вход, если хотя бы одна ветвь вычисления приняла.

Эквивалентность двух определений: ветвление НМТ — это и есть посимвольное угадывание сертификата, а принимающая ветвь — сам сертификат. Обратно: имея верификатор, НМТ недетерминированно выписывает w и запускает V. Отсюда и название: Nondeterministic Polynomial.

Самое частое заблуждение всей темы: NP не расшифровывается как «Non-Polynomial». P ⊆ NP (детерминированная машина — частный случай недетерминированной; либо: сертификат можно игнорировать). Каждая задача из P лежит в NP. Сортировка лежит в NP. Утверждение «эта задача в NP» — это верхняя граница сложности, а не приговор.

Прямые следствия определения

Из определения через перебор сертификатов сразу получаем NP ⊆ EXPTIME: перебрать все 2^p(n) сертификатов, каждый проверить за полином. Это и есть тривиальный алгоритм, который у вас в голове, когда вы говорите «ну можно перебрать».

Известное: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME, и P ≠ EXPTIME (теорема иерархии). Значит хотя бы одно из включений в цепочке строгое — но какое именно, никто не знает. Это очень честная и очень унизительная формулировка состояния науки.

Сведения: единственный настоящий инструмент

Мы не умеем доказывать нижние границы. Зато отлично умеем говорить «эта задача не проще той». Инструмент — сведение.

Определение (сведение по Карпу, many-one, ≤p). A ≤p B, если существует вычислимая за полиномиальное время функция f, такая что для всех x:

x ∈ A   ⟺   f(x) ∈ B

Три вещи, на которых спотыкаются все:

1. Эквивалентность в обе стороны обязательна. Если f переводит «да» в «да», но иногда и «нет» в «да» — это не сведение, а мусор. Доказывая сведение, всегда пишите два направления явно.
2. Направление стрелки контринтуитивно. A ≤p B читается «A не сложнее B», хотя стрелка идёт от A к B. Мнемоника: «я умею решать B — значит умею и A, переведя вход через f». Сводить надо известную трудную задачу к своей, а не наоборот. Обратная ошибка (свёл свою задачу к SAT и объявил её NP-трудной) встречается в статьях и code review постоянно; на самом деле сведение к SAT доказывает лишь принадлежность NP.
3. Транзитивность. A ≤p B и B ≤p C ⟹ A ≤p C, потому что композиция полиномов — полином. Именно это позволяет строить длинные цепочки от SAT к экзотическим задачам.

Сведение по Куку (Turing-сведение, ≤T) слабее по требованиям: A решается полиномиальным алгоритмом с оракулом для B, вызываемым сколько угодно раз. Оно удобнее (позволяет отрицать ответ, комбинировать вызовы), но менее информативно: относительно ≤T классы NP и co-NP склеиваются, и понятие NP-полноты размывается. Для NP-полноты по умолчанию используют сведение по Карпу.

Работающий пример: 3-SAT ≤p INDEPENDENT-SET

Конструкция классическая и красивая. Для формулы в 3-КНФ с m дизъюнктами строим граф:

• каждый литерал каждого дизъюнкта — вершина (всего 3m вершин);
• внутри дизъюнкта соединяем все три вершины (треугольник) — чтобы из дизъюнкта можно было выбрать не более одного литерала;
• между дизъюнктами соединяем противоречащие литералы (x и ¬x) — чтобы выбор был непротиворечивым;
• спрашиваем: есть ли независимое множество размера k = m?

Почему это работает. (⟹) Если формула выполнима, в каждом дизъюнкте есть хотя бы один истинный литерал; берём по одному — получаем m вершин, попарно несмежных (из разных треугольников, и не противоречат друг другу, раз все истинны при одном наборе). (⟸) Если есть независимое множество размера m, то из-за треугольников в нём ровно по одной вершине из каждого дизъюнкта, а из-за рёбер противоречия — набор литералов непротиворечив; доопределяем остальные переменные произвольно и получаем выполняющий набор.

import itertools

def three_sat_to_independent_set(clauses):
    """Сведение 3-SAT ≤p INDEPENDENT-SET.
    clauses: список кортежей литералов, литерал = ненулевое int (-3 означает ¬x3).
    Возвращает (вершины, рёбра, k). Время O((3m)^2) — полином, как и требуется."""
    nodes = [(ci, lit) for ci, cl in enumerate(clauses) for lit in cl]
    edges = set()
    for i in range(len(nodes)):
        for j in range(i + 1, len(nodes)):
            (ci, li), (cj, lj) = nodes[i], nodes[j]
            if ci == cj or li == -lj:      # один дизъюнкт ИЛИ противоречие
                edges.add((i, j))
    return nodes, sorted(edges), len(clauses)

def has_independent_set(n, edges, k):
    """Наивный перебор, C(n, k) сочетаний — только для проверки корректности на игрушках."""
    eset = set(edges)
    for comb in itertools.combinations(range(n), k):
        if all((a, b) not in eset and (b, a) not in eset
               for a, b in itertools.combinations(comb, 2)):
            return comb
    return None

def sat_bruteforce(clauses, nvars):
    for bits in itertools.product([False, True], repeat=nvars):
        assign = {v + 1: bits[v] for v in range(nvars)}
        if all(any(assign[abs(l)] == (l > 0) for l in cl) for cl in clauses):
            return assign
    return None

clauses = [(1, 2, -3), (-1, -2, 3), (1, -2, -3)]
nodes, edges, k = three_sat_to_independent_set(clauses)
print(len(nodes), len(edges), k)               # 9 15 3
print(has_independent_set(len(nodes), edges, k))  # (0, 4, 6) — x1, ¬x2, x1
print(sat_bruteforce(clauses, 3))                 # {1: False, 2: False, 3: False}

Полезное упражнение, которое я прогнал перед публикацией: сгенерировать 300 случайных формул и проверить, что sat_bruteforce(...) is not None совпадает с has_independent_set(...) is not None на каждой. Ноль расхождений — это и есть эмпирическая проверка эквивалентности x ∈ A ⟺ f(x) ∈ B. Всегда так тестируйте свои сведения: ошибка в одном направлении иначе живёт годами.

Дальше INDEPENDENT-SET за одну строчку сводится к VERTEX-COVER (S независимо ⟺ V \ S — вершинное покрытие, поэтому «независимое множество размера k» ⟺ «покрытие размера n−k») и к CLIQUE (независимое множество в G = клика в дополнении G).

NP-полнота и теорема Кука–Левина

Определение. Задача B называется:

• NP-трудной, если A ≤p B для любой A ∈ NP;
• NP-полной, если она NP-трудна и сама лежит в NP.

Смысл: NP-полные задачи — «самые трудные в NP». Если хоть одна из них решится за полином, то P = NP целиком: любую задачу из NP сводим к ней за полином и решаем.

NP-трудная ≠ NP-полная. Проблема остановки NP-трудна (к ней сводится всё), но не в NP — она вообще неразрешима. Оптимизационный TSP («найти кратчайший тур») NP-труден, но формально не NP-полон, потому что это не задача разрешения. Это не педантизм: смешение приводит к утверждениям вида «моя задача NP-полна, значит она в NP, значит решение быстро проверяется» — а для оптимизационной версии проверка оптимальности как раз не очевидно быстрая (она в co-NP-подобной части).

Теорема (Кук 1971, независимо Левин 1973). SAT — задача выполнимости булевой формулы — NP-полна.

Идея доказательства (её стоит понимать, а не помнить): пусть A ∈ NP и M — НМТ, решающая её за n^k шагов. Всё вычисление M на входе x записывается в таблицу («табло») размера n^k × n^k: строка — конфигурация машины в момент времени t. Ключевое наблюдение — локальность: содержимое клетки в строке t+1 зависит только от трёх соседних клеток в строке t (переходная функция смотрит на текущий символ и соседей). Значит корректность всего вычисления выражается конъюнкцией условий на окна 2×3, а каждое такое условие — маленькая булева формула над переменными x[i][j][s] («в клетке (i,j) стоит символ s»). Добавляем условия: первая строка = стартовая конфигурация с входом x, где-то есть принимающее состояние, в каждой клетке ровно один символ. Итог — формула размера poly(n), выполнимая ровно тогда, когда существует принимающая ветвь. Формулу строим за полином. Готово.

Через год Карп (1972) показал, что 21 практическая задача NP-полна, и превратил теорему в индустрию: чтобы доказать NP-полноту новой задачи, достаточно свести к ней одну уже известную NP-полную.

Практический рецепт: как доказать, что задача NP-полна

1. Сформулируйте задачу разрешения. «Существует ли расписание со штрафом ≤ K?» вместо «минимизируйте штраф».
2. Докажите принадлежность NP. Опишите сертификат и верификатор явно, оцените размер сертификата — он обязан быть полиномиальным. Это шаг, который пропускают чаще всего, а он ловит ошибки: например, сертификат «оптимальная стратегия» может быть экспоненциального размера.
3. Выберите источник для сведения. Эвристика: задача про подмножества → VERTEX COVER / SET COVER; про раскладывание по группам → 3-COLORING / PARTITION; про порядок и обход → HAMILTONIAN PATH; про числа → SUBSET SUM; ничего не подходит → 3-SAT.
4. Постройте f и докажите обе импликации. И протестируйте кодом на маленьких экземплярах, как выше.
5. Проверьте, что f полиномиальна — включая размер выхода. Сведение, порождающее граф из 2^n вершин, ничего не доказывает.

Справочник, который до сих пор не устарел: Garey & Johnson, «Computers and Intractability: A Guide to the Theory of NP-Completeness» (1979) — приложение со списком из ~300 NP-полных задач.

co-NP: асимметрия «да» и «нет»

Определение. co-NP = { A : дополнение A лежит в NP }. Это задачи, у которых быстро проверяется ответ «нет».

Канонический пример: TAUTOLOGY — истинна ли формула при всех наборах? Сертификат опровержения (набор, на котором формула ложна) короткий и проверяемый — значит дополнение в NP, значит TAUTOLOGY ∈ co-NP. А вот короткого сертификата тавтологичности никто не знает; по сути гипотеза NP ≠ co-NP эквивалентна утверждению «не существует пропозициональной системы доказательств с полиномиально короткими доказательствами всех тавтологий» (Кук–Рекхоу) — целая область, proof complexity, выросла из этого наблюдения.

Три факта для интуиции:

• P ⊆ NP ∩ co-NP (детерминированный алгоритм даёт сертификаты для обоих ответов — пустые).
• Если NP = co-NP было бы неверно, то P ≠ NP (потому что P замкнут относительно дополнения). Обратное неизвестно.
• Если какая-нибудь NP-полная задача лежит в co-NP, то NP = co-NP. Поэтому задачи из NP ∩ co-NP считаются «скорее лёгкими».

FACTORING — идеальная иллюстрация. Задача «есть ли у N делитель ≤ k?» лежит в NP (сертификат — сам делитель) и в co-NP (сертификат — полное разложение плюс сертификаты простоты сомножителей по Пратту). Значит она в NP ∩ co-NP, и если бы она была NP-полной, то NP = co-NP — чему никто не верит. Вывод, который стоит запомнить: криптография стоит не на NP-полных задачах, а на задачах промежуточной трудности. Это принципиально: NP-полнота говорит о худшем случае, а криптографии нужна трудность в среднем, на случайных ключах.

Теорема Ладнера (1975). Если P ≠ NP, то существуют языки в NP \ P, не являющиеся NP-полными — «NP-промежуточные». Кандидаты: факторизация, дискретный логарифм, изоморфизм графов (после Бабаи 2015 — квазиполиномиальный 2^(log n)^O(1), что почти выводит его в P). https://doi.org/10.1145/321864.321877

Пространство: L, NL, PSPACE и почему память дешевле времени

Память переиспользуема, время — нет. Отсюда весь характер пространственных классов.

Определения.

• L = SPACE(log n) — детерминированная логарифмическая память (на рабочей ленте; вход только для чтения и не считается). Логарифм — это ровно «несколько указателей и счётчиков на вход».
• NL — то же недетерминированно. Полная задача: STCONN (достижимость s → t в ориентированном графе).
• PSPACE = ⋃_k SPACE(n^k).

Базовые соотношения и их доказательства «на пальцах»:

L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME

• NL ⊆ P: граф конфигураций машины с O(log n) памятью имеет 2^O(log n) = poly(n) вершин — обойдём его поиском в ширину за полином.
• NP ⊆ PSPACE: перебираем сертификаты по одному, переиспользуя одну и ту же память под текущий сертификат. Время экспоненциально, память — полином.
• PSPACE ⊆ EXPTIME: у машины с памятью n^k всего 2^O(n^k) различных конфигураций; если она не остановилась за столько шагов — она зациклилась.

Теорема Сэвича (1970). NSPACE(f(n)) ⊆ SPACE(f(n)^2), в частности NPSPACE = PSPACE и NL ⊆ SPACE(log^2 n).

Это поразительный результат: для памяти недетерминизм почти бесплатен, тогда как для времени он предположительно стоит экспоненты. Доказательство — рекурсия «встретимся посередине»: чтобы проверить достижимость за t шагов, переберём среднюю конфигурацию и рекурсивно решим две задачи за t/2 шагов. Глубина рекурсии log t, на каждом уровне храним одну конфигурацию.

def reachable(adj, s, t, steps):
    """Достижимость по Сэвичу: рекурсия «через середину».
    Память: O(глубина рекурсии × размер конфигурации) = O(log(steps) · log n).
    Время: чудовищное, n^O(log n) — классический размен времени на память."""
    if s == t:
        return True
    if steps == 1:
        return t in adj.get(s, ())
    for mid in adj:                                   # перебираем среднюю точку
        if reachable(adj, s, mid, (steps + 1) // 2) \
           and reachable(adj, mid, t, steps // 2):
            return True
    return False

adj = {0: [1], 1: [2], 2: [3], 3: [], 4: [0]}
print(reachable(adj, 0, 3, len(adj)))   # True
print(reachable(adj, 3, 0, len(adj)))   # False

Сравните с обычным BFS: линейное время, но O(n) памяти на очередь и метки. Сэвич даёт O(log^2 n) памяти ценой квазиполиномиального времени. Это тот же trade-off, что между «загрузить датасет в RAM» и «стримить с диска, пересчитывая».

Теорема Иммермана–Селепчени (1987). NSPACE(f) = co-NSPACE(f), то есть NL = co-NL. Недетерминированные пространственные классы замкнуты относительно дополнения — ещё одно свойство, которого мы не знаем для времени (NP = co-NP?). https://doi.org/10.1137/0217058

PSPACE-полнота и игры. Канонически полная задача — TQBF (истинность полностью квантифицированной булевой формулы, ∃x1 ∀x2 ∃x3 ... φ). Чередование кванторов — это в точности чередование ходов двух игроков: «существует мой ход, такой что для всех ответов противника существует мой ход…». Поэтому обобщённые настольные игры с полиномиально ограниченной длиной партии PSPACE-полны (Го с японскими правилами ко, Хекс, Реверси на доске n×n), а игры с экспоненциально длинными партиями — EXPTIME-полны (шахматы n×n). Связь с теорией игр здесь буквальная, а не метафорическая.

Практический смысл PSPACE-полноты для инженера: если ваша задача — это «планирование с чередованием агента и среды» или «верификация против произвольного окружения», она почти наверняка PSPACE-трудна. Планирование в STRIPS, эквивалентность регулярных выражений с оператором ∩, model checking для LTL — всё это PSPACE-полные задачи, и в отличие от NP они сопротивляются даже сертификатам.

Что мы знаем точно: теоремы иерархии

Единственный класс безусловных разделений — диагонализация (та же техника, что у Кантора и Тьюринга).

Теорема об иерархии по времени (Хартманис и Стернс, 1965). Для «конструируемых по времени» f:

DTIME(f(n))  строго ⊊  DTIME(f(n) · log f(n))

Следствия: P ⊊ EXPTIME, DTIME(n^2) ⊊ DTIME(n^3). То есть больше времени действительно даёт больше вычислительной силы.

Теорема об иерархии по памяти. Аналогично, но плотнее: SPACE(f) ⊊ SPACE(g) при f = o(g). Следствия: L ⊊ PSPACE, PSPACE ⊊ EXPSPACE.

Комбинируя, получаем то немногое, что известно наверняка:

P ≠ EXPTIME          NL ≠ PSPACE          PSPACE ≠ EXPSPACE          L ≠ PSPACE

И одновременно не доказано ни одно из: P ≠ NP, NP ≠ PSPACE, P ≠ PSPACE, L ≠ P, L ≠ NP. Последнее особенно отрезвляет: неизвестно даже, нужна ли SAT-у память больше логарифмической.

Почему P vs NP не поддаётся: три барьера

Это не «математики ещё не постарались». Известны три метатеоремы, каждая из которых хоронит целый класс подходов.

1. Релятивизация (Бейкер, Гилл, Соловей, 1975). Существуют оракулы A и B с P^A = NP^A и P^B ≠ NP^B. Любое доказательство, работающее «через симуляцию машин как чёрных ящиков» (диагонализация, включая все техники из теорем иерархии), релятивизуется — то есть осталось бы верным при любом оракуле. Раз обе стороны реализуемы оракулами, такое доказательство невозможно. https://doi.org/10.1137/0204037

2. Естественные доказательства (Разборов, Рудич, 1994). Почти все известные нижние границы для схем используют свойство функций, которое (а) конструктивно проверяемо, (б) выполняется для большой доли всех функций. Такие «естественные» свойства при разумных криптографических предположениях (существование псевдослучайных функций) не могут отделить P от NP: они автоматически ломали бы криптографию. То есть либо криптостойкости нет, либо доказательство обязано быть «неестественным». https://doi.org/10.1006/jcss.1997.1494

3. Алгебризация (Ааронсон, Вигдерсон, 2008). Интерактивные доказательства и арифметизация (техника, давшая IP = PSPACE и обошедшая релятивизацию) тоже имеют свой барьер.

Практический вывод для инженера: когда вам присылают доказательство P ≠ NP на трёх страницах, спросите, какой из трёх барьеров оно обходит и как. Если ответа нет — доказательства нет. Обзор Скотта Ааронсона «P =? NP» — лучшее чтение по теме: https://www.scottaaronson.com/papers/pnp.pdf

Соседние классы, которые встречаются в работе

Два результата отсюда стоит знать наизусть:

Теорема Тоды (1991): PH ⊆ P^#P. Вся полиномиальная иерархия сводится к одному оракулу подсчёта. Подсчёт — по-настоящему мощная операция; отсюда трудность точного вероятностного вывода в байесовских сетях (#P-полон), о чём подробнее в теории вероятностей.

Теорема PCP (Арора, Сафра, Арора–Лунд–Мотвани–Судан–Сегеди, 1992): каждый язык из NP имеет вероятностно проверяемое доказательство, где верификатор читает константное число бит доказательства, используя O(log n) случайных бит. Следствие, которое реально важно инженеру: неаппроксимируемость. Для MAX-3SAT никакой полиномиальный алгоритм не даёт гарантии лучше 7/8 (если P ≠ NP, Håstad); для SET COVER — лучше (1−o(1))·ln n; для общего TSP без неравенства треугольника — никакой константы вообще. То есть «сделаю приближённо» — не универсальная отмазка, у приближений тоже есть жёсткие границы. https://doi.org/10.1145/278298.278306

Моя задача NP-полна. Что дальше?

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

Ключевые ходы подробнее:

• Точный экспоненциальный, но умный. 2^n вместо n! — огромная разница. TSP через DP Хелда–Карпа: O(2^n · n^2) времени и O(2^n · n) памяти — реально считает 20–25 городов точно. Всегда спрашивайте: «а какая именно экспонента?»
• Параметризованная сложность (FPT). Разделите сложность на «размер входа» и «сложность структуры»: алгоритм f(k) · poly(n) при маленьком k практичен даже при огромном n. VERTEX COVER решается за O(1.28^k + k·n). Ключевой параметр для графовых задач — древесная ширина (treewidth): при tw = w куча NP-полных задач решается за 2^O(w) · n. Свободная книга: Cygan et al., «Parameterized Algorithms» — https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf
• Особые случаи. 2-SAT в P (импликационный граф + компоненты сильной связности), 3-SAT NP-полон. Раскраска в 2 цвета — P, в 3 — NP-полна. Максимальное паросочетание — P, максимальное независимое множество — NP-полно. Граница проходит по неожиданным местам, и часто ваш реальный вход лежит с лёгкой стороны.
• Решатели. Современные CDCL SAT-решатели проглатывают промышленные экземпляры с миллионами переменных: конфликт-ориентированное обучение клауз, нерегулярные рестарты, эвристика VSIDS. Худший случай экспоненциален, средний по реальным задачам — вполне терпим. Смотрите SAT Competition (https://satcompetition.github.io/) и Google OR-Tools CP-SAT (https://developers.google.com/optimization/cp).

def dpll(clauses, assign):
    """Мини-DPLL: распространение единичных клауз + ветвление.
    Ядро всех CDCL-решателей — они добавляют сверху обучение клауз и рестарты.
    Худший случай O(2^n), на структурированных экземплярах — практичен."""
    # выбрасываем удовлетворённые клаузы и ложные литералы
    clauses = [c for c in clauses if not any(assign.get(abs(l)) == (l > 0) for l in c)]
    clauses = [tuple(l for l in c if abs(l) not in assign) for c in clauses]
    if not clauses:
        return assign                       # все клаузы удовлетворены
    if any(len(c) == 0 for c in clauses):
        return None                         # конфликт: пустая клауза
    unit = next((c[0] for c in clauses if len(c) == 1), None)
    if unit is not None:                    # unit propagation — главный источник скорости
        return dpll(clauses, {**assign, abs(unit): unit > 0})
    lit = clauses[0][0]                     # ветвление
    for val in (lit > 0, not (lit > 0)):
        r = dpll(clauses, {**assign, abs(lit): val})
        if r is not None:
            return r
    return None

print(dpll([(1, 2, -3), (-1, -2, 3), (1, -2, -3), (-1,)], {}))  # {1: False, 2: True, 3: False}
print(dpll([(1,), (-1,)], {}))                                  # None

Худший случай — это не типичный случай. Диаграмма ниже — карта, которую полезно держать в голове при оценке задачи:

Где эта теория всплывает в реальном коде

• Компиляторы. Распределение регистров — раскраска графа интерференции (Chaitin, 1982, https://doi.org/10.1145/800230.806984); планирование инструкций и выбор инструкций тоже NP-трудны. Поэтому LLVM использует линейное сканирование и эвристики, а не оптимум.
• Базы данных. Выбор порядка соединений — NP-трудная задача; PostgreSQL при from_collapse_limit/geqo_threshold (по умолчанию 12 отношений) переключается с DP на генетический алгоритм. См. https://www.postgresql.org/docs/current/geqo.html — это буквально теория сложности, выставленная в конфиг.
• Типы. Вывод типов в Hindley–Milner полон для DEXPTIME (Mairson, 1990, https://doi.org/10.1145/96709.96748) — да, экспоненциален в худшем случае, но человеческие программы не строят патологические цепочки let. Проверка типов с зависимыми типами или полиморфизмом высших рангов быстро становится неразрешимой. Подробности — в теории вычислимости.
• Криптография. См. выше: нужна трудность в среднем и односторонние функции; P ≠ NP необходимо, но недостаточно. Инструментарий — конечные поля и группы из абстрактной алгебры.
• Машинное обучение. Обучение даже трёхнейронной сети точно — NP-трудно (Blum & Rivest, 1992); отбор признаков, обучение оптимального дерева решений, точный вывод в байесовских сетях (#P) — всё трудное. Отсюда и градиентный спуск: мы отказались от оптимума в пользу локального минимума, и это осознанный размен, а не небрежность.
• DevOps и сборка. Разрешение зависимостей = SAT; планирование задач на кластере = bin packing; размещение подов с ограничениями = вариант обобщённого назначения. Kubernetes-планировщик — это набор эвристик поверх NP-трудной задачи.
• Тестирование. Минимизация тест-сьюта при заданном покрытии — SET COVER; отсюда логарифмическая гарантия жадного алгоритма и невозможность существенно лучшей (по PCP).

Типичные заблуждения

1. «NP = не полиномиально». Нет: N — от недетерминизма, и P ⊆ NP.
2. «NP-полная задача нерешаема». Решаема, просто (предположительно) не за полином в худшем случае. SAT с миллионом переменных решается ежедневно в EDA-индустрии.
3. «Я свёл свою задачу к SAT — значит она NP-трудна». Наоборот: это доказывает задача ∈ NP. Для трудности сводить надо к вашей задаче от известной трудной.
4. «NP-трудно = NP-полно». Полнота требует ещё и принадлежности NP. Проблема остановки и TQBF NP-трудны, но не NP-полны.
5. «P = NP означало бы конец криптографии завтра». Небуквально: доказательство может быть неконструктивным, а алгоритм — n^100. Но большинство исследователей считает, что практическое P = NP действительно разрушило бы асимметричную криптографию.
6. «Псевдополиномиальный алгоритм = полиномиальный». DP для рюкзака за O(nW) экспоненциален от длины входа. Разница видна на числах в 2^64.
7. «Аппроксимация всегда спасает». Теорема PCP говорит: для многих задач гарантированное приближение лучше конкретного порога само NP-трудно.
8. «Квантовый компьютер решит NP-полные задачи». Алгоритм Гровера даёт квадратичное ускорение перебора (2^(n/2)) — заметно, но не полином. NP ⊆ BQP считается неверным.
9. «Раз задача в P, она практична». n^6 на миллионе элементов — это тоже приговор. P — теоретическая граница, а не SLA.

Мини-итог

• Сложность меряют от длины входа в битах, в худшем случае, асимптотически, и класс «за полином» устойчив к смене модели вычисления.
• P — быстро решить; NP — быстро проверить ответ «да»; co-NP — быстро проверить «нет»; PSPACE — уложиться в полиномиальную память, где недетерминизм почти бесплатен (Сэвич).
• Единственный работающий инструмент — сведения по Карпу; NP-полнота = «NP-трудно + лежит в NP»; фундамент всей конструкции — теорема Кука–Левина через табло вычисления.
• Безусловно известны только «дальние» разделения из теорем иерархии (P ≠ EXPTIME, L ≠ PSPACE); ни одно соседнее включение не доказано строгим, а три барьера объясняют почему.
• Практически NP-полнота — это указание сменить стратегию: точный экспоненциальный при малом n, FPT при малом параметре, аппроксимация с гарантией, промышленный решатель или частный случай с хорошей структурой.

Источники:

• Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach — черновик открыт: https://theory.cs.princeton.edu/complexity/book.pdf
• Michael Sipser. Introduction to the Theory of Computation — лучшее первое чтение по Кук–Левину и Сэвичу.
• Michael Garey, David Johnson. Computers and Intractability (1979) — каталог NP-полных задач.
• Stephen Cook. The Complexity of Theorem-Proving Procedures (1971): https://dl.acm.org/doi/10.1145/800157.805047
• Richard Karp. Reducibility Among Combinatorial Problems (1972): https://doi.org/10.1007/978-1-4684-2001-2_9
• Официальная постановка задачи тысячелетия P vs NP (Cook, Clay Institute): https://www.claymath.org/millennium/p-vs-np/
• Complexity Zoo — справочник по 500+ классам: https://complexityzoo.net/Complexity_Zoo
• Scott Aaronson. P =? NP (обзор барьеров и текущего состояния): https://www.scottaaronson.com/papers/pnp.pdf

Что дальше

Мы говорили о том, сколько ресурсов нужно для решения задачи, но всё время оставляли в тени вопрос, какие вообще бывают модели вычисления слабее машины Тьюринга и что они умеют. Конечные автоматы, магазинные автоматы, контекстно-свободные грамматики — это не только теория: на них стоят лексеры, парсеры, регулярные выражения и валидаторы протоколов, и именно там пролегает граница между «регуляркой можно» и «регуляркой нельзя».

Следующая статья: Автоматы, формальные языки и грамматики.