Теория сложности: P vs NP

Мотивация: не только вычислимо, но и быстро

Проблема остановки неразрешима совсем. Но большинство практических задач вычислимы — вопрос в том, насколько быстро. Теория сложности изучает ресурсы (время, память), требуемые алгоритмами. Проблема P = NP? — важнейший открытый вопрос информатики: совпадают ли задачи, решения которых быстро находятся, с теми, решения которых быстро проверяются?

Классы сложности

P (Polynomial Time): L ∈ P, если ∃ детерминированная МТ M и полином p: M разрешает L за время O(p(|w|)) при любом входе w.

Примеры в P: сортировка массива (O(n log n)), поиск кратчайшего пути (алгоритм Дейкстры O(n²)), проверка простоты числа (алгоритм AKS, 2002, O((log n)^{12})).

NP (Nondeterministic Polynomial Time): L ∈ NP, если ∃ «верификатор» V (детерминированная МТ) с полиномиальным временем такой, что: w ∈ L ⟺ ∃ «сертификат» c (|c| ≤ poly(|w|)): V(w,c) = «принять».

Примеры в NP: SAT (сертификат = выполняющая оценка), задача коммивояжёра (сертификат = маршрут), раскраска графа в k цветов (сертификат = раскраска).

P ⊆ NP: если задача решается быстро — можно и быстро верифицировать (сертификат = само решение, верификатор = алгоритм). Обратное неизвестно — P = NP?

NP-полнота

NP-сложная задача L: любая L' ∈ NP сводится к L за полиномиальное время (L' ≤ₚ L).

NP-полная задача: L ∈ NP и L — NP-сложная.

Теорема Кука–Левина (1971/72): SAT — NP-полна. Это первая NP-полная задача. Идея: для любой NDTM M и входа w строим формулу φ_{M,w} ∈ КНФ так, что φ выполнима ⟺ M принимает w.

Через сведения из SAT доказана NP-полнота: 3-SAT, CLIQUE, независимое множество, гамильтонов путь, задача коммивояжёра, целочисленное программирование, ...

Проблема P ≠ NP

Консенсус сообщества: P ≠ NP, но доказательства нет. Если P = NP:

RSA и эллиптическая криптография сломаны (задача факторизации ∈ NP).
Автоматическое доказательство теорем: найти доказательство = не сложнее проверить.
Оптимизация: тысячи NP-задач решаются за полиномиальное время.

Численный пример

Задача: Проверить, что 3-COLORABILITY (раскраска графа в 3 цвета) ∈ NP, и найти раскраску конкретного графа K₄ (или объяснить, почему её нет).

Шаг 1. K₄ — полный граф на 4 вершинах (все 4·3/2 = 6 рёбер). Хроматическое число χ(K₄) = 4 (каждая пара смежна, нужны 4 разных цвета). K₄ не раскрашивается в 3 цвета.

Шаг 2. Граф K₄ {одно ребро} — удалим ребро (1,4). Можно ли раскрасить в 3 цвета? Вершина 1 и 2 смежны: разные цвета, пусть 1→A, 2→B. Вершина 3 смежна с 1 (A) и 2 (B): 3→C. Вершина 4 смежна с 2 (B) и 3 (C), но не с 1 (A): 4→A. Раскраска: 1→A, 2→B, 3→C, 4→A. 3-красима ✓.

Шаг 3. Проверка — верификатор V: дан граф G и раскраска c (сертификат). Проверить, что для каждого ребра (u,v): c(u) ≠ c(v). За O(m) шагов (m — число рёбер) → V работает за полиномиальное время → 3-COLORABILITY ∈ NP ✓.

Реальное приложение

Расписание экзаменов: задача создания расписания без конфликтов (один студент — несколько предметов) — это раскраска графа конфликтов. Задача NP-полна; на практике используют эвристики (генетические алгоритмы, имитация отжига).

Дополнительные аспекты

Гипотеза P ≠ NP — открытая центральная проблема теоретической информатики и одна из семи задач тысячелетия с премией $1 млн. Полиномиальные алгоритмы существуют для базовых задач (сортировка, кратчайшие пути, минимальное покрывающее дерево, линейное программирование). NP-полные задачи (3-SAT, 3-COLOR, Hamiltonian Cycle, TSP в decision-форме) полиномиально сводятся друг к другу, и эффективное решение любой даёт эффективное решение всех. Практически принимают P ≠ NP и используют приближённые алгоритмы (PTAS, FPTAS) или эвристики (метаэвристики, ML-driven решатели). Криптография с открытым ключом (RSA, ECDSA) опирается на предположение, что определённые задачи (факторизация, дискретный логарифм) трудны — без P ≠ NP вся современная цифровая безопасность рухнула бы.

Связь с другими разделами математики

Классы P и NP естественно пересекаются с алгеброй и комбинаторикой через результаты типа теоремы Ловаса о перфектных графах: доказательство использует полиномиальные алгоритмы для задач, близких к раскраске и максимальному клику в специальных классах графов. Алгебраическая геометрия входит в игру в работах Бласа, Шпиляна и др., исследующих сложность решений систем полиномиальных уравнений над различными полями; здесь NP-полные задачи кодируются как система уравнений, а геометрические инварианты отражают «жёсткость» задачи.

Теория вероятностей появляется в вероятностных алгоритмах и классах BPP, RP, ZPP. Работы Гиллеса, Лавина и Колмогорова заложили основу случайных алгоритмов, а теорема Шнорра–Адлемана о вероятностном тесте простоты предвосхитила детерминированный алгоритм AKS. Современная теория псевдослучайности и хеш-функций опирается на гипотезы о неравенстве P и NP, связывая вычислительную сложность с теорией вероятностных неравенств и концентрацией меры.

Дифференциальные уравнения и численные методы связаны через анализ сложности задач решения ОДУ и ЧДУ. Работы Трауба и Воссена показали, что даже приближённое решение уравнений может иметь экспоненциальную по размеру входа сложность. В оптимизации граница между эффективными (P) и потенциально трудными (NP-полными) задачами проходит между линейным программированием, для которого алгоритм Хачияна и внутренняя точка Кармаркара дают полиномиальное время, и нелинейным или целочисленным программированием, описанным в монографиях Шрика и Немировского как фундаментально связанное с NP-полнотой.

Историческая справка и развитие идеи

Корни современной теории сложности уходят к работам Тьюринга (1936) и Поста, сформулировавших понятие алгоритмической вычислимости. В 1960-е годы Хартманис и Стирнс в статье 1965 года в журнале Transactions of the AMS ввели классы по времени и памяти и доказали первые теоремы иерархии. Стивен Кук в 1971 году в журнале Information and Control сформулировал класс NP и теорему о полноте SAT; независимо Леонид Левин опубликовал аналогичные идеи в СССР несколько позже, в 1973 году. В середине 1970-х Ричард Карп в знаменитой статье 1972 года перечислил 21 NP-полную задачу, систематизировав технику полиномиальных сведений. В те же годы Кнут, Гэри и Джонсон выпустили фундаментальный справочник «Computers and Intractability» (1979), ставший стандартом. К рубежу 1980–1990-х проблема P vs NP стала центральной в теоретической информатике. Работы Фейгена, Пападимитриу, Арора и Сафры привели к теореме PCP, связывающей NP-полноту с трудностью аппроксимации. В 2000 году Клэйовский математический институт включил P vs NP в список задач тысячелетия.