От формулы к графу: сведение 3-SAT к независимому множеству

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

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

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

Попробуй до чтения придумать, что должно стать вершиной и что ребром, чтобы вопрос о графе совпал с вопросом о формуле. Подсказка: ребро означает «эти две вершины нельзя взять вместе». Что в формуле нельзя сделать вместе? Объявить истинными x и ¬x. А что нужно сделать обязательно? В каждой скобке найти хотя бы один истинный литерал.

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

Выбор представителей. От каждой рабочей группы на общее собрание идёт один человек. Группы - скобки, люди в них - литералы. Некоторые люди из разных групп терпеть друг друга не могут - это x и ¬x - и вместе на собрание не пойдут.

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

Механизм: построение и доказательство в обе стороны

Дана формула из m скобок, в каждой не больше трёх литералов. Построение работает и для длинных скобок; тройки взяты потому, что цепочка сведений идёт через 3-SAT, а группы из трёх вершин удобнее рисовать.

вершины   по одной на каждое вхождение литерала в формулу
рёбра 1   между каждыми двумя вершинами одной скобки
          (из скобки берём не больше одной)
рёбра 2   между вершинами литералов x и ¬x из разных скобок
          (нельзя выбрать и x, и ¬x)
число k   m - число скобок

Скобка из трёх литералов превращается в треугольник, из двух - в ребро, из одного - в отдельную вершину.

Формула выполнима → есть независимое множество размера m. Возьмём выполняющий набор. В каждой скобке есть хотя бы один истинный литерал; выберем по одному такому и возьмём их вершины. Вершин m. Две из них не могут лежать в одной скобке: брали по одной. И не могут быть литералами x и ¬x: оба истинны при одном наборе, а x и ¬x одновременно истинными не бывают. Рёбер между выбранными вершинами нет.

Есть независимое множество размера m → формула выполнима. В независимом множестве не больше одной вершины от каждой скобки - внутри скобки все вершины соединены. Вершин m, скобок m: значит, ровно по одной от каждой. Объявим литералы выбранных вершин истинными. Противоречия не возникнет: вершины x и ¬x соединены ребром и вместе в множество не попали. Переменным, которые не задеты, дадим любые значения. В каждой скобке теперь есть истинный литерал.

Размер. Вершин не больше 3m, рёбер не больше числа пар вершин: построение полиномиально.

Итак, 3-SAT ≤ независимое множество. Задача о независимом множестве лежит в NP - сертификат - сами вершины. Значит, она NP-полна. А дальше работают сведения из третьего урока:

любая задача из NP  ≤  SAT  ≤  3-SAT  ≤  независимое множество
                           независимое множество  ≤  вершинное покрытие
                           независимое множество  ≤  клика

Вторая и третья строки - ответвления от независимого множества: оно сводится и к вершинному покрытию, и к клике.

Все три задачи о графах NP-полны.

Правило

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

Разбор: граф для трёх скобок

Формула (x₁ ∨ x₂ ∨ x₃)(¬x₁ ∨ ¬x₂ ∨ x₃)(x₁ ∨ ¬x₂ ∨ ¬x₃). Функция postroit возвращает список литералов по вершинам и список рёбер. Вершины нумеруются подряд: 0, 1, 2 - первая скобка, 3, 4, 5 - вторая, 6, 7, 8 - третья. Рёбра напечатаны двумя группами: внутри скобок и между скобками. Раз в каждой скобке здесь ровно три литерала, номер скобки при печати - это номер вершины, делённый нацело на три; для скобок разной длины нужен список skobka_vershiny. В функции nezavisimoe буква m - не число скобок, а копия маски для подсчёта единиц.

def postroit(formula):
    literaly = []
    skobka_vershiny = []
    for nomer in range(len(formula)):
        for literal in formula[nomer]:
            literaly.append(literal)
            skobka_vershiny.append(nomer)
    ryobra = []
    for a in range(len(literaly)):
        for b in range(a + 1, len(literaly)):
            if (skobka_vershiny[a] == skobka_vershiny[b]
                    or literaly[a] == -literaly[b]):
                ryobra.append([a, b])
    return [literaly, ryobra]

graf = postroit([[1, 2, 3], [-1, -2, 3], [1, -2, -3]])
print(graf[0])
vnutri = []
mezhdu = []
for r in graf[1]:
    if r[0] // 3 == r[1] // 3:
        vnutri.append(r)
    else:
        mezhdu.append(r)
print(len(vnutri), len(mezhdu))
print(vnutri)
print(mezhdu)

[1, 2, 3, -1, -2, 3, 1, -2, -3]
9 6
[[0, 1], [0, 2], [1, 2], [3, 4], [3, 5], [4, 5], [6, 7], [6, 8], [7, 8]]
[[0, 3], [1, 4], [1, 7], [2, 8], [3, 6], [5, 8]]

Девять вершин, три треугольника - девять рёбер внутри скобок. Между скобками шесть рёбер, и каждое - противоречие: вершина 0 - это x₁, вершина 3 - ¬x₁; вершина 1 - x₂, вершины 4 и 7 - ¬x₂; вершины 2 и 5 - x₃, вершина 8 - ¬x₃; вершина 3 - ¬x₁, вершина 6 - снова x₁.

Чего в списке нет: ребра между вершинами 2 и 5. Обе - литерал x₃, и взять их вместе можно: это значит всего лишь, что x₃ делает истинными две скобки сразу. Рёбра соединяют противоречащие литералы, а не одинаковые переменные.

Независимое множество размера три здесь, например, {0, 4, 6}: x₁ из первой скобки, ¬x₂ из второй, x₁ из третьей. Набор x₁ = истина, x₂ = ложь, а x₃ любое.

Разбор: решаем формулу графом и возвращаем набор

Теперь всё вместе: построить граф, найти независимое множество размера m перебором, перевести его обратно в значения переменных. Перебор экспоненциален, и это не изъян демонстрации: сведение не решает задачу, а переносит её. Три формулы: выполнимая, невыполнимая и со скобками разной длины.

def postroit(formula):
    literaly = []
    skobka_vershiny = []
    for nomer in range(len(formula)):
        for literal in formula[nomer]:
            literaly.append(literal)
            skobka_vershiny.append(nomer)
    ryobra = []
    for a in range(len(literaly)):
        for b in range(a + 1, len(literaly)):
            if (skobka_vershiny[a] == skobka_vershiny[b]
                    or literaly[a] == -literaly[b]):
                ryobra.append([a, b])
    return [literaly, ryobra]

def nezavisimoe(vershin, ryobra, k):
    for maska in range(2 ** vershin):
        razmer = 0
        m = maska
        while m > 0:
            razmer = razmer + m % 2
            m = m // 2
        if razmer != k:
            continue
        goditsya = True
        for r in ryobra:
            if maska >> r[0] & 1 == 1 and maska >> r[1] & 1 == 1:
                goditsya = False
                break
        if goditsya:
            return maska
    return -1

def reshit(formula, n):
    graf = postroit(formula)
    maska = nezavisimoe(len(graf[0]), graf[1], len(formula))
    if maska == -1:
        return [len(graf[0]), len(graf[1]), "невыполнима"]
    nabor = [False] * (n + 1)
    for v in range(len(graf[0])):
        if maska >> v & 1 == 1 and graf[0][v] > 0:
            nabor[graf[0][v]] = True
    return [len(graf[0]), len(graf[1]), nabor[1:]]

print(reshit([[1, 2, 3], [-1, -2, 3], [1, -2, -3]], 3))
print(reshit([[1, 2], [-1, 2], [1, -2], [-1, -2]], 2))
print(reshit([[1, -2, 3], [-1, 2], [-3], [2, 3]], 3))

[9, 15, [True, False, False]]
[8, 12, 'невыполнима']
[8, 10, [True, True, False]]

В каждой строке - число вершин, число рёбер и ответ. Первая формула - из прошлого разбора: найден набор x₁ = истина, остальные ложны. Переменные, чьи положительные литералы не выбраны, получили «ложь»; противоречия нет, потому что выбранные литералы друг другу не противоречат.

Вторая формула - все четыре скобки из двух переменных: (x₁ ∨ x₂)(¬x₁ ∨ x₂)(x₁ ∨ ¬x₂)(¬x₁ ∨ ¬x₂). Каждый набор значений нарушает ровно одну из них. В графе восемь вершин и двенадцать рёбер, и независимого множества размера четыре в нём нет: формула невыполнима, и граф это подтверждает.

Третья формула содержит скобку из одного литерала - она стала вершиной без рёбер внутри скобки, и её приходится брать обязательно. Найденный набор: x₁ и x₂ истинны, x₃ ложна.

Общий рисунок этой конструкции повторяется в большинстве доказательств NP-полноты. Есть устройства выбора - здесь треугольники: из каждого нужно взять ровно одну вершину. Есть устройства согласованности - рёбра между x и ¬x: выбор в одном месте ограничивает выбор в другом. И есть число k, подобранное так, чтобы уклониться от выбора было нельзя.

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

Забыты рёбра между скобками. Тогда независимое множество размера m есть всегда - по вершине из каждого треугольника, - и граф отвечает «да» на любую формулу.

Ребро проведено между одинаковыми литералами. Вершины x₃ из двух скобок соединять нельзя: одна переменная вправе выполнять много скобок. С лишними рёбрами выполнимые формулы получают ответ «нет».

Число k взято неверно. При k меньше m какая-то скобка остаётся без представителя, и из множества не следует выполнимость.

Доказана одна сторона. «Из выполняющего набора получается множество» - половина. Без второй половины неизвестно, не появится ли множество у невыполнимой формулы.

Сведение проведено в обратную сторону. Свести независимое множество к 3-SAT можно, но это покажет лишь, что независимое множество не труднее 3-SAT, - что и так известно про любую задачу из NP.

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

Опознание трудной задачи. «Выбрать по одному из каждой группы без конфликтов» - расписание экзаменов, назначение частот передатчикам, распределение переменных программы по немногим быстрым ячейкам процессора, регистрам, - это независимое множество или раскраска на графе конфликтов: вершины - объекты, ребро - «эти два нельзя вместе», цвет - выбранный день, частота или регистр. Раскраску разбирает следующая глава. Увидев такую форму, знаешь, чего ждать.

Собственные доказательства. Когда нужно показать, что новая задача NP-полна, ищут в ней устройство выбора и устройство согласованности. Чаще всего сводят 3-SAT или одну из графовых задач; каталог следующей главы помогает выбрать, с чего начать.

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

Теперь сам

1. Сколько вершин и рёбер внутри скобок в графе для формулы из пяти скобок по три литерала?
2. Формула: (x₁ ∨ x₂)(¬x₁)(¬x₂). Построй граф и скажи, есть ли в нём независимое множество размера 3.
3. Почему между двумя вершинами литерала x₃ из разных скобок ребра нет?
4. В графе нашлось независимое множество с вершинами ¬x₁, x₂, ¬x₄. Какие значения переменных из него следуют?
5. Как из этого сведения получить NP-полноту задачи о клике?