NP-полнота и теорема Кука-Левина: самая трудная задача в NP существует

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

Как думаешь, есть ли в NP самая трудная задача

В NP тысячи задач из разных областей: формулы, графы, числа, расписания, головоломки. Сведения позволяют сравнивать их по трудности.

Ответь себе до чтения: может ли найтись одна задача, к которой сводятся все остальные задачи класса, - включая те, что ещё не придуманы? Звучит неправдоподобно: откуда задаче о формулах знать про задачи о расписаниях. Тем не менее такая задача есть, и она не одна: NP-полных задач известны тысячи, и все они в точном смысле равны по трудности. Вопрос о P и NP - это вопрос об одной-единственной из них, любой.

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

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

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

Механизм: определения, теорема и что она даёт

Задача B NP-трудна, если каждая задача из NP полиномиально сводится к B. Задача NP-полна, если она NP-трудна и сама лежит в NP.

NP-трудная    не легче любой задачи из NP;  сама может лежать и вне NP
NP-полная     NP-трудная и в NP:  самая трудная среди задач класса

Сразу следует: если хоть одна NP-полная задача решается за полиномиальное время, то P = NP. И наоборот: если P ≠ NP, ни одна NP-полная задача полиномиального алгоритма не имеет.

Теорема Кука-Левина. Задача SAT NP-полна.

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

Идея в три шага.

1. Вход x задан. Проверка V(x, c) - вычисление полиномиальной длины.
   Его можно развернуть в схему из вентилей: входы схемы - биты
   сертификата c, выход - «принять». Сам x вшит в схему постоянными
   значениями: для каждого x схема и формула свои.
   Схема строится слоями, по слою на шаг проверки: память программы -
   набор битов, и слой вычисляет каждый бит после шага по битам до шага.
   Слоёв столько, сколько шагов в худшем случае. Ветвления и циклы
   исчезают: слой считает оба варианта, а нужный выбирают те же вентили
   по биту условия. Шагов - многочлен; за столько шагов больше многочлена
   памяти не занять; поэтому и вентилей - многочлен от длины x.

2. Каждому вентилю заводим переменную - значение на его выходе -
   и пишем скобки, которые истинны ровно тогда, когда вентиль сработал
   правильно:
       g = a и b       (¬g ∨ a) (¬g ∨ b) (g ∨ ¬a ∨ ¬b)
       g = a или b     (g ∨ ¬a) (g ∨ ¬b) (¬g ∨ a ∨ b)
       g = не a        (g ∨ a) (¬g ∨ ¬a)

3. Добавляем скобку из одного литерала: выход схемы истинен.

Проверить скобки вентиля можно перебором четырёх пар значений a и b. Для «или»: если a или b истинна, одна из первых двух скобок требует истинной g; если обе ложны, третья требует ложной g. Получилась формула в КНФ - из скобок, соединённых «и», - длина которой - многочлен от длины x. Она выполнима тогда и только тогда, когда существует сертификат, который V принимает, то есть когда ответ на x - «да». Перевод сделан, и он не зависел от того, о чём была задача.

Что теорема даёт на практике. До неё, чтобы доказать NP-трудность, нужно было бы сводить к задаче все задачи из NP. После неё достаточно одного сведения:

чтобы доказать, что задача B NP-полна:
    1. показать, что B лежит в NP: назвать сертификат и проверку
    2. свести к B какую-нибудь известную NP-полную задачу A
тогда любая задача из NP  ≤  A  ≤  B

3-SAT. Задача 3-SAT - выполнимость формул, в которых каждая скобка содержит не больше трёх литералов. Она NP-полна: в NP она лежит как частный случай SAT, и к ней сводится SAT. Длинную скобку режут на короткие, вводя вспомогательные переменные:

(a ∨ b ∨ c ∨ d ∨ e)      →      (a ∨ b ∨ y₁) (¬y₁ ∨ c ∨ y₂) (¬y₂ ∨ d ∨ e)

Переменная y₁ разрешает первой скобке быть истинной без a и b, но тогда вторая скобка обязана найти истинный литерал дальше. Если в исходной скобке есть истинный литерал, вспомогательные переменные подбираются так: истинны все до скобки с этим литералом и ложны все после; если все литералы ложны, первая скобка требует y₁, вторая тогда требует y₂, а третья остаётся ложной.

Граница проходит между двумя и тремя: 2-SAT, где в скобке не больше двух литералов, решается за линейное время через компоненты сильной связности. Тем же приёмом тройку до пар не разрезать: отщепив от тройки литерал, получаем два литерала плюс новую переменную - снова тройку.

Правило

Задача NP-полна, если она лежит в NP и к ней сводится любая задача из NP. Теорема Кука-Левина: SAT NP-полна, потому что работу проверяющей программы можно записать формулой полиномиального размера. Чтобы доказать NP-полноту новой задачи, показывают, что она в NP, и сводят к ней известную NP-полную. 3-SAT NP-полна, 2-SAT лежит в P.

Разбор: схема превращается в формулу

Схема голосования: три входа, выход равен единице, когда единиц на входах не меньше двух. Вентили: g₄ = x₁ и x₂, g₅ = x₁ и x₃, g₆ = x₂ и x₃, g₇ = g₄ или g₅, g₈ = g₇ или g₆. Функция ventil_v_skobki выдаёт скобки для одного вентиля; программа собирает формулу, добавляет требование «выход истинен» и перебором находит все выполняющие наборы.

def ventil_v_skobki(vyhod, operaciya, a, b):
    if operaciya == "и":
        return [[-vyhod, a], [-vyhod, b], [vyhod, -a, -b]]
    if operaciya == "или":
        return [[vyhod, -a], [vyhod, -b], [-vyhod, a, b]]
    return [[vyhod, a], [-vyhod, -a]]

def istinna(formula, kod):
    for skobka in formula:
        goditsya = False
        for literal in skobka:
            znachenie = kod >> (abs(literal) - 1) & 1 == 1
            if (literal > 0) == znachenie:
                goditsya = True
        if not goditsya:
            return False
    return True

shema = [[4, "и", 1, 2], [5, "и", 1, 3], [6, "и", 2, 3],
         [7, "или", 4, 5], [8, "или", 7, 6]]
formula = []
for v in shema:
    for skobka in ventil_v_skobki(v[0], v[1], v[2], v[3]):
        formula.append(skobka)
formula.append([8])
print(len(formula), formula[:4])
vhody = []
for kod in range(2 ** 8):
    if istinna(formula, kod):
        vhody.append(str(kod & 1) + str(kod >> 1 & 1)
                     + str(kod >> 2 & 1))
print(len(vhody), vhody)

16 [[-4, 1], [-4, 2], [4, -1, -2], [-5, 1]]
4 ['011', '110', '101', '111']

Пять вентилей дали пятнадцать скобок, шестнадцатая - требование к выходу. Первые три скобки описывают вентиль g₄: «если g₄ истинна, то истинна x₁», «если g₄ истинна, то истинна x₂», «если истинны обе, то истинна g₄».

Из 256 наборов значений восьми переменных формулу выполняют четыре, и входы в них - 011, 110, 101, 111 (первая цифра - x₁; порядок задают значения переменных вентилей, поэтому он не по возрастанию): ровно те, где единиц не меньше двух. Наборов четыре, а не больше, потому что значения переменных вентилей однозначно определяются входами: формула не оставляет им свободы.

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

Разбор: длинные скобки режутся на тройки

Функция v_tri выполняет сведение SAT к 3-SAT: пока в скобке больше трёх литералов, отщепляет два первых и вводит новую переменную. Функция vypolnyayushchie перебором находит, какие значения исходных переменных встречаются среди выполняющих наборов, - чтобы сравнить формулу до и после.

def v_tri(formula, n):
    novaya = []
    for skobka in formula:
        ostatok = skobka
        while len(ostatok) > 3:
            n = n + 1
            novaya.append([ostatok[0], ostatok[1], n])
            ostatok = [-n] + ostatok[2:]
        novaya.append(ostatok)
    return [novaya, n]

def vypolnyayushchie(formula, n, pervyh):
    najdeno = set()
    for kod in range(2 ** n):
        goditsya = True
        for skobka in formula:
            est = False
            for literal in skobka:
                if (literal > 0) == (kod >> (abs(literal) - 1) & 1 == 1):
                    est = True
            if not est:
                goditsya = False
                break
        if goditsya:
            najdeno.add(kod % 2 ** pervyh)
    return sorted(najdeno)

dlinnaya = [[1, 2, 3, 4, 5], [-1, -2], [-3, -4, -5, 1]]
itog = v_tri(dlinnaya, 5)
print(itog[0])
print(itog[1])
do = vypolnyayushchie(dlinnaya, 5, 5)
print(do == vypolnyayushchie(itog[0], itog[1], 5), len(do))
for k in [4, 6, 8, 20]:
    odna = []
    for i in range(1, k + 1):
        odna.append(i)
    r = v_tri([odna], k)
    print(k, len(r[0]), r[1] - k)

[[1, 2, 6], [-6, 3, 7], [-7, 4, 5], [-1, -2], [-3, -4, 8], [-8, -5, 1]]
8
True 21
4 2 1
6 4 3
8 6 5
20 18 17

Скобка из пяти литералов превратилась в три скобки с новыми переменными 6 и 7; скобка из четырёх - в две с переменной 8; короткая скобка осталась как была; во второй строке вывода - сколько переменных стало. Третья строка - проверка: наборы значений первых пяти переменных, при которых формула выполнима, до и после перевода совпадают, их 21 из 32.

Последние четыре строки - размер: скобка из k литералов даёт k − 2 скобки и k − 3 новые переменные. По числу литералов формула выросла меньше чем втрое - было k, стало 3(k − 2), - перевод линеен - полиномиальность сведения здесь очевидна.

Обрати внимание, что именно сохраняется. Формулы не равносильны: в новой больше переменных. Сохраняется ответ на вопрос «выполнима ли» - ровно то, что требует определение сведения.

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

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

«NP-полная - значит нерешаемая». Она разрешима: перебор сертификатов всегда даёт ответ. Вопрос только во времени.

«NP-полнота доказана - значит быстрого алгоритма нет». Доказано другое: быстрый алгоритм для неё означал бы P = NP. Что P ≠ NP, не доказано.

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

Задачу пытаются свести к SAT, чтобы доказать её трудность. К SAT сводится всё из NP, включая вопрос «отсортирован ли массив». Сводить нужно SAT или другую NP-полную задачу к своей.

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

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

Решатели выполнимости. Самая трудная задача класса оказалась и самой полезной: современные решатели справляются с формулами из миллионов переменных, возникающими при проверке микросхем и программ. Перевести задачу в SAT и отдать решателю - рабочий инструмент, а не теоретический приём.

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

Теперь сам

1. Что нужно показать, чтобы доказать NP-полноту новой задачи B?
2. Запиши скобки для вентиля g = a или b.
3. Разбей скобку (a ∨ b ∨ c ∨ d) на скобки не длиннее трёх литералов.
4. Сколько скобок и новых переменных получится из скобки в десять литералов?
5. Для NP-полной задачи нашли алгоритм со временем n³. Что из этого следует?