Полиномиальное сведение: одна задача в одежде другой

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

Как думаешь, сколько кода нужно

У тебя есть готовая программа: по графу и числу k она отвечает, есть ли в графе k вершин, никакие две из которых не соединены ребром. Заказчику нужно другое: можно ли выбрать не больше k вершин так, чтобы у каждого ребра хотя бы один конец был выбран.

Ответь себе до чтения: сколько придётся написать, чтобы решить вторую задачу, пользуясь первой программой? Одну строку. Вершины, не вошедшие в покрытие, попарно не соединены: будь между двумя из них ребро, оно осталось бы непокрытым. И наоборот: если вершины множества попарно не соединены, у каждого ребра хотя бы один конец лежит вне его, то есть остальные вершины - покрытие. Значит, покрытие не больше чем из k вершин есть ровно тогда, когда есть n − k попарно несоединённых вершин. Вторая задача - это первая, прочитанная с другого конца.

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

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

Прибор - задача A, розетка - программа для задачи B, переходник - перевод. Если переходник есть и розетка работает, прибор включится. А если известно, что прибор не включить никак, значит, не работает и розетка: иначе переходник помог бы.

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

Полиномиальное сведение задачи A к задаче B - алгоритм f, который:

работает за время, полиномиальное от длины входа
любой вход x задачи A превращает во вход f(x) задачи B
сохраняет ответ:   на x ответ «да»   ⇔   на f(x) ответ «да»

Пишут A ≤ B и читают «A не труднее B».

A ≤ B  и  B в P     →  A в P:    перевести вход и решить B
A ≤ B  и  A не в P  →  B не в P: иначе по строке выше A была бы в P
A ≤ B  и  B ≤ C     →  A ≤ C:    два перевода подряд,
                                 многочлен от многочлена

Условие сохранения ответа двустороннее, и доказывать нужно обе стороны: что из «да» получается «да» и что из «нет» получается «нет». Вторую половину удобнее доказывать как «если на f(x) ответ да, то и на x был да». Это то же самое утверждение: будь на x ответ «нет», а на f(x) - «да», оно бы нарушилось.

Три задачи о графе с n вершинами. В блоке под ними ⇄ значит «сводятся друг к другу в обе стороны», а ⇔ - «тогда и только тогда».

Независимое множество: есть ли k вершин, никакие две из которых не соединены ребром.

Вершинное покрытие: есть ли не больше k вершин таких, что у каждого ребра хотя бы один конец среди них.

Клика: есть ли k вершин, каждые две из которых соединены ребром.

независимое множество ⇄ вершинное покрытие
    S независимо   ⇔   все вершины, кроме S, образуют покрытие
    перевод входа: граф тот же,  k заменить на n − k
    при k больше n перевод выдаёт заготовленный вход: в сторону
    покрытия - с ответом «нет», в обратную - с ответом «да»

независимое множество ⇄ клика
    S независимо в графе G   ⇔   S - клика в дополнении G
    перевод входа: рёбра заменить на отсутствующие рёбра,  k то же

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

Почему сведение обязано быть быстрым. Если разрешить переводу работать сколько угодно, любая разрешимая задача сведётся к любой другой, у которой есть и вход с ответом «да», и вход с ответом «нет»: перевод сам решит задачу её же алгоритмом и выдаст заранее заготовленный вход с нужным ответом. Ограничение по времени заставляет перевод быть именно переводом.

Правило

A ≤ B, если полиномиальный алгоритм превращает каждый вход A во вход B с тем же ответом. Из A ≤ B следует: быстрая программа для B даёт быструю для A, а трудность A означает трудность B. Сведения складываются в цепочки. Доказательство сведения состоит из трёх частей: перевод полиномиален, «да» переходит в «да», «нет» переходит в «нет».

Разбор: три задачи на одном графе

Проверим оба сведения перебором на графе с семью вершинами. Множество вершин хранится маской, как в разделе о битах. Функции проверяют три свойства; цикл перебирает все 128 масок и запоминает наибольшее независимое множество, наименьшее покрытие и наибольшую клику в дополнении.

def razmer(maska):
    k = 0
    while maska > 0:
        k = k + maska % 2
        maska = maska // 2
    return k

def vershiny(maska):
    spisok = []
    v = 0
    while maska >> v > 0:
        if maska >> v & 1 == 1:
            spisok.append(v)
        v = v + 1
    return spisok

def nezavisimo(ryobra, maska):
    for r in ryobra:
        if maska >> r[0] & 1 == 1 and maska >> r[1] & 1 == 1:
            return False
    return True

def pokryvaet(ryobra, maska):
    for r in ryobra:
        if maska >> r[0] & 1 == 0 and maska >> r[1] & 1 == 0:
            return False
    return True

def klika(n, ryobra, maska):
    for a in range(n):
        for b in range(a + 1, n):
            if (maska >> a & 1 == 1 and maska >> b & 1 == 1
                    and [a, b] not in ryobra):
                return False
    return True

def dopolnenie(n, ryobra):
    novye = []
    for a in range(n):
        for b in range(a + 1, n):
            if [a, b] not in ryobra:
                novye.append([a, b])
    return novye

n = 7
ryobra = [[0, 1], [1, 2], [1, 3], [1, 4], [2, 3],
          [3, 4], [3, 5], [3, 6], [4, 6]]
drugoj = dopolnenie(n, ryobra)
nezavisimoe = 0
pokrytie = 2 ** n - 1
klika_v_dopolnenii = 0
for maska in range(2 ** n):
    if nezavisimo(ryobra, maska) and razmer(maska) > razmer(nezavisimoe):
        nezavisimoe = maska
    if pokryvaet(ryobra, maska) and razmer(maska) < razmer(pokrytie):
        pokrytie = maska
    if (klika(n, drugoj, maska)
            and razmer(maska) > razmer(klika_v_dopolnenii)):
        klika_v_dopolnenii = maska
print(razmer(nezavisimoe), razmer(pokrytie), n)
ostalnye = 2 ** n - 1 - nezavisimoe
print(vershiny(nezavisimoe), vershiny(ostalnye),
      pokryvaet(ryobra, ostalnye))
print(len(drugoj), vershiny(klika_v_dopolnenii))

4 3 7
[0, 2, 4, 5] [1, 3, 6] True
12 [0, 2, 4, 5]

Наибольшее независимое множество - четыре вершины, наименьшее покрытие - три, вместе семь: 4 + 3 = n. Вторая строка показывает само соответствие: независимы вершины 0, 2, 4, 5, а оставшиеся 1, 3, 6 покрывают все девять рёбер. В дополнении графа двенадцать рёбер - из двадцати одной пары вычли девять - и наибольшая клика в нём - те же вершины 0, 2, 4, 5.

Поиск независимого множества и поиск клики в дополнении нашли одни и те же вершины {0, 2, 4, 5}, а остальные вершины {1, 3, 6} - покрытие наименьшего размера. Сам поиск покрытия остановился на другом покрытии из трёх вершин, {1, 3, 4}: наименьших покрытий у этого графа два, и размер у них один. Программа, быстро решающая любую из трёх задач, решала бы и две другие; и если хоть одна из них трудна, трудны все три.

Разбор: частный случай внутри общей задачи

Самое частое сведение на практике - заметить, что знакомая задача является частным случаем новой.

Покрытие множествами: дан набор элементов и несколько их подмножеств; можно ли выбрать не больше k подмножеств так, чтобы каждый элемент попал хотя бы в одно.

Вершинное покрытие - частный случай: элементы - рёбра графа, а подмножество, отвечающее вершине, - рёбра, которые из неё выходят. Выбрать вершины, покрывающие все рёбра, - то же, что выбрать подмножества, покрывающие все элементы. Функция svesti строит такой вход, а число k перевод оставляет прежним; вторая функция решает покрытие множествами перебором; если покрыть все элементы нельзя, она вернёт число на единицу больше числа подмножеств.

def razmer(maska):
    k = 0
    while maska > 0:
        k = k + maska % 2
        maska = maska // 2
    return k

def naimenshee_pokrytie_mnozhestvami(vsego, mnozhestva):
    luchshee = len(mnozhestva) + 1
    for maska in range(2 ** len(mnozhestva)):
        pokryto = set()
        for i in range(len(mnozhestva)):
            if maska >> i & 1 == 1:
                for element in mnozhestva[i]:
                    pokryto.add(element)
        if len(pokryto) == vsego and razmer(maska) < luchshee:
            luchshee = razmer(maska)
    return luchshee

def svesti(n, ryobra):
    mnozhestva = []
    for v in range(n):
        svoi = []
        for nomer in range(len(ryobra)):
            if v in ryobra[nomer]:
                svoi.append(nomer)
        mnozhestva.append(svoi)
    return mnozhestva

n = 7
ryobra = [[0, 1], [1, 2], [1, 3], [1, 4], [2, 3],
          [3, 4], [3, 5], [3, 6], [4, 6]]
mnozhestva = svesti(n, ryobra)
print(mnozhestva)
print(naimenshee_pokrytie_mnozhestvami(len(ryobra), mnozhestva))

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

Семь подмножеств - по одному на вершину; в каждом номера рёбер этой вершины. Наименьшее покрытие - три подмножества, как и наименьшее вершинное покрытие в прошлом разборе.

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

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

Перепутано направление. «Моя задача сводится к SAT» говорит, что твоя задача не труднее SAT, и ничего - о том, что она трудна. Чтобы доказать трудность, сводят известную трудную задачу к своей.

Доказана одна половина. Показано, что решение исходной задачи даёт решение новой, а обратное пропущено. Тогда на входах с ответом «нет» перевод может выдавать входы с ответом «да».

Перевод раздувает вход. Если f(x) экспоненциально длиннее x, быстрая программа для B на таком входе работает экспоненциально долго относительно x, и вывод «A решается быстро» не получается.

Сведение принято за равносильность. A ≤ B - это «не труднее», а не «такая же». Равносильны задачи, сводимые в обе стороны, как три задачи первого разбора.

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

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

Оценивать новую задачу. Если в ней как частный случай сидит известная трудная, она не легче. Обычно это видно за пять минут и экономит недели попыток найти точный быстрый алгоритм.

Переносить алгоритмы. Сведение к задаче из P - готовый алгоритм: так паросочетания решались через потоки, а системы разностных ограничений - через кратчайшие пути.

Теперь сам

1. В графе 20 вершин, наибольшее независимое множество - 8. Каков размер наименьшего вершинного покрытия?
2. Как по графу и числу k получить вход задачи о клике с тем же ответом, что у задачи о независимом множестве?
3. Известно A ≤ B и B лежит в P. Что можно сказать об A? А если известно только, что A лежит в P?
4. Кто-то свёл свою задачу к задаче о кратчайшем пути. Что он доказал?
5. Почему перевод «перебрать все подмножества вершин и выдать ответ» не считается сведением?