Классы P и NP

Разрешимость говорит, можно ли решить задачу. Теория сложности — за разумное ли время. Здесь живут классы P и NP.

P — задачи, решаемые за полиномиальное время. NP — задачи, для которых предложенное решение можно проверить за полиномиальное время.

Полиномиальное = «практично»

Все задачи в этом разделе разрешимы — вопрос в эффективности. Принято считать «эффективным» алгоритм, время которого ограничено многочленом от размера входа: O(n), O(n²), O(n³) и т.п. Такие задачи образуют класс P (polynomial). Противоположность — экспоненциальное время O(2ⁿ), которое взрывается мгновенно: при n=100 это больше, чем атомов во Вселенной. Граница «полином / экспонента» — практическая граница между «решаемо» и «безнадёжно» для больших входов.

Примеры из P: сортировка, поиск кратчайшего пути (Дейкстра), проверка простоты числа (доказано в 2002), большинство задач из школьного курса алгоритмов.

NP: проверить легко, найти трудно

Класс NP (недетерминированно-полиномиальный) — задачи, где, если кто-то подсказал ответ (сертификат), его проверка занимает полином. Классический пример — SAT: можно ли подобрать значения переменных, чтобы булева формула стала истинной? Найти набор трудно (вроде бы нужен перебор 2ⁿ), но проверить предложенный набор — мгновенно: подставил и посчитал. Другой пример — судоку: решить трудно, проверить готовое решение легко.

P:  «решить» за полином               (нашёл сам, быстро)
NP: «проверить решение» за полином    (дали ответ — проверил быстро)

очевидно: P ⊆ NP  (если можешь решить, можешь и проверить — реши и сравни)
вопрос века: P = NP ?  (правда ли проверка не легче решения?)

Проверка сертификата на Python

Покажем суть NP на примере «суммы подмножества» (subset sum): есть ли среди чисел подмножество с заданной суммой? Найти подмножество — потенциально экспоненциально. А вот проверить предложенное — мгновенно.

numbers = [3, 7, 1, 8, 4]
target = 15

# ПРОВЕРКА сертификата (за полином) — это и есть суть NP
def verify(certificate):
    return sum(certificate) == target and \
           all(x in numbers for x in certificate)

# кто-то «подсказал» решение [3, 8, 4]
print("сертификат [3,8,4] верен?", verify([3, 8, 4]))   # 3+8+4=15
print("сертификат [7,1] верен?  ", verify([7, 1]))      # 7+1=8 ≠ 15

# ПОИСК решения — перебор всех подмножеств (экспонента)
from itertools import combinations
found = None
for r in range(len(numbers)+1):
    for combo in combinations(numbers, r):
        if sum(combo) == target:
            found = combo; break
    if found: break
print("найденное подмножество:", found)

Вывод:

сертификат [3,8,4] верен? True
сертификат [7,1] верен?   False
найденное подмножество: (7, 8)

Проверка сертификата — один проход, полином. Поиск же перебирает подмножества — 2ⁿ вариантов. Эта асимметрия «проверить легко / найти трудно» и определяет NP.

Как работает под капотом

Откуда буква «N» (недетерминированный)? Исходное определение NP: задачи, решаемые недетерминированной машиной Тьюринга за полином. Такая машина (как НКА из второго раздела!) «угадывает» правильный путь и проверяет его. Угадывание сертификата + полиномиальная проверка — две стороны одной монеты. Недетерминизм здесь — не реальное железо, а способ формализовать «удачную догадку». Реальный детерминированный компьютер вынужден перебирать догадки, отсюда подозрение на экспоненту.

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

«NP = не-полиномиальные». Нет! NP — это «недетерминированно-полиномиальные». P ⊆ NP: все P-задачи лежат в NP. NP — не «трудные», а «проверяемые за полином».

Считать, что NP-задачи нерешаемы. Они разрешимы (можно перебрать), просто, возможно, медленно. Это про скорость, не про вычислимость.

Путать P и NP с разрешимостью. И P, и NP — внутри разрешимых задач. Проблема остановки вообще вне этих классов — она неразрешима.

Итог

P — задачи, решаемые за полиномиальное время (практически эффективные).
NP — задачи, где предложенное решение проверяется за полином (проверить легко, найти, возможно, трудно).
P ⊆ NP очевидно; равны ли они — открытый вопрос.
Имя NP — от недетерминированной машины Тьюринга, «угадывающей» сертификат.