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

Если ты определишь NP через сертификат и проверяющую программу, назовёшь сертификаты для трёх задач и объяснишь, почему у ответа «нет» сертификата может не быть, - листай до «Теперь сам».

Как думаешь, одинаково ли трудно найти и проверить

Тебе дают заполненную сетку судоку и спрашивают, правильно ли она заполнена. Это минута: пройти по строкам, столбцам и квадратам. Потом дают пустую сетку того же размера и просят заполнить.

Ответь себе до чтения: бывают ли задачи, где проверить готовый ответ принципиально легче, чем найти его, - не «мы пока не придумали как», а доказанно? Кажется очевидным, что бывают. Но доказательства нет. Все знают задачи, где проверка занимает секунды, а лучший известный поиск - века; никто не доказал, что быстрого поиска для них не существует. Этому вопросу больше полувека.

На что это похоже

Пазл из тысячи деталей. Собирать - вечер или неделя. Убедиться, что собран, - один взгляд: картинка сложилась, дыр нет.

Собранный пазл - свидетельство того, что его можно собрать. Оно убеждает кого угодно и сразу, и неважно, как его получили: терпением, удачей или подсказкой. А вот убедить кого-то, что пазл собрать нельзя, когда все детали на месте, а картинка не складывается, так не получится: предъявлять нечего.

Механизм: сертификат и проверяющая программа

Задача разрешения принадлежит классу NP, если есть проверяющая программа V с двумя входами - условием x и сертификатом c - такая, что:

V работает за время, полиномиальное от длины x
если ответ на x - «да»,   то существует сертификат c полиномиальной
                          длины, на котором V(x, c) = «принять»
если ответ на x - «нет»,  то V(x, c) = «отвергнуть» при любом c

Сертификат - подсказка, которой проверяющая программа не доверяет: она убеждается сама. Ложным сертификатом её не обмануть, а отсутствие подходящего сертификата и означает ответ «нет».

задача                       сертификат            проверка
выполнима ли формула         значения переменных   подставить и вычислить
есть ли в графе цикл         порядок вершин        каждая один раз,
через все вершины                                  рёбра есть
есть ли подмножество чисел   номера выбранных      сложить
с суммой S                   чисел
составное ли число           делитель              разделить
раскрашивается ли граф       цвет каждой вершины   концы рёбер
в три цвета                                        разного цвета

Формулы. Формула записана в конъюнктивной нормальной форме, КНФ, если она - несколько скобок, соединённых «и», а в каждой скобке - литералы, соединённые «или». Литерал - переменная или её отрицание. Задача выполнимости, SAT: есть ли набор значений переменных, при котором истинны все скобки. В программах скобка - список чисел: 3 - это x₃, -3 - отрицание x₃.

Второе определение. NP - задачи, которые решает недетерминированная машина Тьюринга из главы о моделях за полиномиальное время (временем считается самая длинная ветка): она угадывает сертификат и проверяет его. Отсюда название: nondeterministic polynomial. Определения равносильны; угадывание - способ сказать «сертификат существует».

Что известно о соотношении классов.

P ⊆ NP      задачу из P проверять не нужно: программа решает её сама,
            сертификат пуст
NP ⊆ EXP    перебрать все сертификаты: у сертификата длиной p(n) бит
            вариантов 2 в степени p(n), и каждый проверяется
            за полиномиальное время
P ≠ EXP     доказано
P = NP ?    неизвестно

Здесь EXP - задачи, решаемые за время 2 в степени многочлена от длины входа. Раз P ≠ EXP, хотя бы одно из двух включений - P в NP или NP в EXP - не равенство. Какое именно, не знает никто.

Дополнения. Дополнение задачи - тот же вопрос с перевёрнутым ответом. Класс co-NP - задачи, у которых короткий проверяемый сертификат есть для ответа «нет». Вопрос «невыполнима ли формула» лежит в co-NP: ответ «нет» на него значит, что формула выполнима, и подтверждает это выполняющий набор. А как коротко доказать, что формула невыполнима? Общего способа не известно. Совпадают ли NP и co-NP, тоже неизвестно.

Правило

Задача лежит в NP, если для каждого входа с ответом «да» существует сертификат полиномиальной длины, который полиномиальная программа проверяет, а для входа с ответом «нет» никакой сертификат проверку не проходит. P ⊆ NP ⊆ EXP. Определение несимметрично: о сертификатах ответа «нет» оно ничего не обещает.

Разбор: проверить набор и найти набор

Функция proverit получает формулу и набор значений и считает, сколько литералов пришлось посмотреть. Функция perebor ищет выполняющий набор, перебирая все 2ⁿ вариантов, и считает, сколько наборов проверено. Значение переменной i лежит в nabor[i]; нулевой элемент не используется. Запись kod >> i & 1 == 1 читается как ((kod >> i) & 1) == 1: сдвиг раньше &, а & раньше сравнения.

def proverit(formula, nabor):
    proverok = 0
    for skobka in formula:
        istinna = False
        for literal in skobka:
            proverok = proverok + 1
            if literal > 0 and nabor[literal]:
                istinna = True
            if literal < 0 and not nabor[-literal]:
                istinna = True
        if not istinna:
            return [False, proverok]
    return [True, proverok]

def perebor(formula, n):
    naborov = 0
    for kod in range(2 ** n):
        nabor = [False]
        for i in range(n):
            nabor.append(kod >> i & 1 == 1)
        naborov = naborov + 1
        if proverit(formula, nabor)[0]:
            return [nabor[1:], naborov]
    return [[], naborov]

formula = [[1, 2, -3], [-1, 3], [-2, -3], [2, 3]]
print(proverit(formula, [False, True, False, True]),
      proverit(formula, [False, True, True, True]))
print(perebor(formula, 3))
for n in [4, 8, 10]:
    cepochka = [[1]]
    for i in range(1, n):
        cepochka.append([-i, i + 1])
    vse_istinny = perebor(cepochka, n)
    cepochka.append([-n])
    print(n, vse_istinny[1], perebor(cepochka, n))

[True, 9] [False, 7]
[[False, True, False], 3]
4 16 [[], 16]
8 256 [[], 256]
10 1024 [[], 1024]

Формула из четырёх скобок: (x₁ ∨ x₂ ∨ ¬x₃)(¬x₁ ∨ x₃)(¬x₂ ∨ ¬x₃)(x₂ ∨ x₃). Значок ∨ - «или», ¬ - отрицание, стоящие рядом скобки соединены «и». Набор «истина, ложь, истина» проверен за девять взглядов на литералы; набор «истина, истина, истина» отвергнут на седьмом - третья скобка ложна. Проверка стоит не больше длины формулы. Вторая строка вывода - перебор: он остановился на третьем по счёту наборе, «ложь, истина, ложь». Он тоже выполняющий; у этой формулы таких наборов два.

Дальше формула-цепочка: x₁, затем «из x₁ следует x₂», «из x₂ следует x₃» и так далее. Выполняет её единственный набор - все переменные истинны, и перебор находит его последним: 16, 256, 1024 набора. Если добавить скобку ¬xₙ, формула становится невыполнимой, и перебор проходит все наборы, чтобы в этом убедиться.

Про цепочку нужно сказать честно: человек видит ответ сразу, и есть алгоритм, который решает такие формулы за линейное время. Перебор глуп, а не задача трудна. Утверждение «для SAT в общем случае ничего принципиально лучше перебора не известно» относится к формулам без такой удобной структуры - и оно именно «не известно», а не «доказано, что нет».

Разбор: три сертификата и один, которого нет

Три проверяющие программы: для цикла через все вершины, для суммы подмножества и для составного числа. Каждая получает условие и сертификат. Слишком длинный сертификат суммы отвергается сразу: время проверки должно зависеть от условия, а не от того, что прислали.

def cikl_goditsya(n, ryobra, poryadok):
    if len(poryadok) != n or len(set(poryadok)) != n:
        return False
    for i in range(n):
        a = poryadok[i]
        b = poryadok[(i + 1) % n]
        if [a, b] not in ryobra and [b, a] not in ryobra:
            return False
    return True

def summa_goditsya(chisla, cel, vybrannye):
    if len(vybrannye) > len(chisla):
        return False
    summa = 0
    for i in vybrannye:
        if i < 0 or i >= len(chisla):
            return False
        summa = summa + chisla[i]
    return len(set(vybrannye)) == len(vybrannye) and summa == cel

def sostavnoe(n, d):
    return 1 < d and d < n and n % d == 0

ryobra = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 0], [0, 2], [1, 4]]
print(cikl_goditsya(5, ryobra, [0, 2, 3, 4, 1]),
      cikl_goditsya(5, ryobra, [0, 3, 1, 2, 4]))
chisla = [267, 493, 869, 961, 1000, 1153, 1246, 1598, 1766, 1922]
print(summa_goditsya(chisla, 7035, [1, 2, 4, 5, 7, 9]),
      summa_goditsya(chisla, 7035, [0, 1, 2]))
print(sostavnoe(1000001, 101), sostavnoe(1000003, 101))

True False
True False
True False

В каждой строке сначала верный сертификат, потом негодный. Порядок 0, 2, 3, 4, 1 - цикл через все пять вершин; порядок 0, 3, 1, 2, 4 отвергнут: ребра между 0 и 3 нет. Шесть чисел с номерами 1, 2, 4, 5, 7, 9 дают в сумме 7035; подмножеств у десяти чисел 1024, а проверка одного - шесть сложений. Число 1 000 001 делится на 101.

Теперь последний вызов: sostavnoe(1000003, 101) вернул False. Что это значит? Только то, что 101 - не делитель. Число 1 000 003 простое, и ни один сертификат проверку не пройдёт, но одна неудачная попытка этого не показывает. Чтобы убедить кого-то в ответе «нет» этим способом, пришлось бы перебрать все делители.

Для простоты чисел короткие сертификаты ответа «нет, не составное» всё-таки существуют - они устроены хитрее делителя, - и, более того, простота проверяется за полиномиальное время. Для невыполнимости формул и отсутствия цикла через все вершины неизвестно, существуют ли короткие сертификаты для всех входов. Это и есть вопрос о NP и co-NP.

Что ломается без этого

«NP - это неполиномиальные задачи». Нет: N - от слова «недетерминированный». В NP лежит весь класс P, включая вопросы «отсортирован ли массив» и «есть ли путь между вершинами».

«Задача из NP - значит трудная». Принадлежность NP - верхняя оценка: задача не труднее, чем «угадать и проверить». Трудными называют самые трудные задачи в NP, и им посвящены следующие уроки.

Сертификат путают с решением оптимизационной задачи. «Этот маршрут кратчайший» одним маршрутом не подтверждается: нужно ещё убедить, что короче нет. В NP лежит вопрос с порогом: «есть ли маршрут не длиннее k».

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

Зачем это в работе

Узнавать форму. «Найти объект, про который легко проверить, что он годится» - расписание без накладок, раскладка по контейнерам, набор тестов с полным покрытием - это задача из NP. Такую форму стоит распознать до того, как обещаны сроки.

Недоверенный решатель. Раз проверка дешёвая, искать решение можно чем угодно - эвристикой, сторонней программой, случайным поиском, - а потом проверить результат своей короткой программой. Так устроены решатели выполнимости и системы, выдающие вместе с ответом его обоснование.

Криптография. Подпись легко проверить и трудно подделать; пароль легко сверить с хешем и трудно подобрать. Весь этот инженерный мир стоит на предположениях того же рода, только более сильных: что существуют функции, которые легко вычислить и трудно обратить. Из одного P ≠ NP это ещё не следует.

Теперь сам

1. Что служит сертификатом в задаче «есть ли в графе независимое множество размера не меньше k»?
2. Лежит ли в NP задача «отсортирован ли массив»?
3. Формула: (x₁ ∨ x₂)(¬x₁ ∨ x₂)(¬x₂). Выполнима ли она?
4. Почему задача «является ли данный цикл через все вершины кратчайшим в графе с длинами рёбер» не выглядит задачей из NP?
5. Что означало бы равенство P = NP для задач из таблицы в этом уроке?