ETH и SETH: сколько экспоненты не убрать

Если ты сформулируешь ETH и SETH, объяснишь, почему сведение должно раздувать вход линейно, чтобы переносить границу 2^o(n), и знаешь, что из SETH следует для расстояния редактирования, листай до «Теперь сам».

Как думаешь, насколько может помочь гений

Лучший известный алгоритм для 3-SAT работает примерно за 1,307ⁿ. Перебор - 2ⁿ. Может, завтра кто-нибудь придумает 1,1ⁿ или 1,01ⁿ? Это всё ещё экспонента, P ≠ NP её не запрещает.

Ответь себе до чтения: имеет ли значение, 1,3ⁿ или 1,01ⁿ? При бюджете в миллиард операций первое доходит до 77 переменных, второе - до двух тысяч. Разница огромная, и её не описывает ни P, ни NP. ETH отвечает на этот вопрос предположением: основу опустить можно, но не до единицы - никакой 2^o(n). И из одного этого предположения выводятся точные пределы для десятков задач.

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

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

ETH - такая «гипотеза о шаге» для экспоненциального времени. Сравнение маршрутов - сведения: если 3-SAT переводится в задачу без большого раздувания, задача не может быть заметно быстрее 3-SAT.

Механизм: размер сведения переносит границу

ETH. Существует c > 0, такое, что 3-SAT на n переменных не решается за 2^(c·n). Лемма о прореживании (Импальяццо, Патури, Зейн) добавляет: можно считать, что скобок O(n) - то есть граница относится и к длине формулы.

Перенос через сведение. Пусть 3-SAT с n переменными сводится к задаче B с входом размера N:

N = O(n)    (линейное раздувание)  →  B не решается за 2^o(N)
N = O(n²)                          →  B не решается за 2^o(√N)
параметр k = O(n)                  →  B не решается за 2^o(k) · poly

Следствия ETH:

независимое множество, покрытие, 3-раскраска    не 2^o(n)
вершинное покрытие по размеру k                 не 2^o(k) · poly
клика по размеру k                              не f(k) · n^o(k)
путь из k вершин                                не 2^o(k) · poly
плоские графы: независимое множество и др.      не 2^o(√n)
    (алгоритмы 2^O(√n) есть: ширина плоского графа O(√n))

SETH. Для любого ε > 0 есть k, при котором k-SAT не решается за (2 − ε)ⁿ: перебор для общей выполнимости почти оптимален. Из SETH выводятся пределы и для полиномиальных задач: расстояние редактирования и наибольшая общая подпоследовательность не считаются за n^(2 − ε) (Бакурс, Индик, 2015; Брингманн, Кюннеманн, 2015). Сведение строит из формулы две строки длины около 2^(n/2).

Правило

ETH: 3-SAT не решается за 2^o(n). Сведение с линейным раздуванием переносит эту границу на другую задачу; квадратичное - даёт 2^o(√N). Отсюда: вершинное покрытие не 2^o(k), клика не f(k) · n^o(k), задачи на плоских графах не 2^o(√n). SETH: k-SAT при больших k не быстрее (2 − ε)ⁿ; из неё - квадратичная нижняя граница для расстояния редактирования.

Разбор: что значит основа экспоненты

Сколько переменных уложится в миллиард операций при разной основе, и плоские графы: если алгоритм работает за 2^(√N), где √N - ширина, его показатель сравнивается с показателем бюджета.

import math

budzhet = 10 ** 9
for osnova in [2.0, 1.308, 1.1, 1.01]:
    n = math.log(budzhet) / math.log(osnova)
    print(osnova, int(n))
for N in [100, 400, 1600]:
    # плоский граф из N вершин: ширина около √N
    print(N, int(math.sqrt(N)), int(math.log2(budzhet)))

2.0 29
1.308 77
1.1 217
1.01 2082
100 10 29
400 20 29
1600 40 29

Перебор - 29 переменных, лучший известный - 77, гипотетическая основа 1,01 - больше двух тысяч. ETH разрешает любую из этих основ, но не разрешает «основу, стремящуюся к единице с ростом n».

Плоские графы: на 1600 вершинах ширина бывает до порядка 40 (это оценка сверху - у плоского дерева она 1), и 2⁴⁰ уже больше бюджета 2²⁹, а на 400 вершинах ширина 20 - укладывается. Для плоских графов это и есть предел: ETH запрещает 2^o(√n), а динамика по разложению даёт 2^O(√n) - совпадение с точностью до константы в показателе.

Разбор: квадратичная таблица и SETH

Расстояние редактирования из раздела о строках: таблица n × n. Считаем заполненные клетки на строках длины 20, 40, 80.

def rasstoyanie(a, b, schet):
    pred = list(range(len(b) + 1))
    for i in range(1, len(a) + 1):
        tek = [i] + [0] * len(b)
        for j in range(1, len(b) + 1):
            schet[0] = schet[0] + 1
            zamena = pred[j - 1]
            if a[i - 1] != b[j - 1]:
                zamena = zamena + 1
            tek[j] = min(pred[j] + 1, tek[j - 1] + 1, zamena)
        pred = tek
    return pred[len(b)]

for n in [20, 40, 80]:
    a = ("abcab" * n)[:n]
    b = ("bcabc" * n)[:n]
    schet = [0]
    print(n, rasstoyanie(a, b, schet), schet[0])

20 5 400
40 9 1600
80 17 6400

Удвоение длины - учетверение клеток: n². Можно ли быстрее? Известны ускорения в логарифм раз (метод четырёх русских), но не n^1,99. SETH объясняет, почему: алгоритм за n^(2 − ε) для расстояния редактирования дал бы алгоритм для k-SAT за (2 − δ)ⁿ при всех k - против SETH. Квадратичная таблица, которую курс показал в разделе о динамическом программировании, - не недоработка, а, скорее всего, предел.

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

Сводят с большим раздуванием и делают вывод «не 2^o(n)». Если из n переменных получилось n² вершин, граница только 2^o(√N). Размер сведения - часть вывода.

Считают ETH доказанной. Это гипотеза, сильнее P ≠ NP. Выводы из неё - условные, хотя никто не ожидает их опровержения.

Ищут 2^o(√n) для задач на плоских графах. При ETH его нет: 2^O(√n) уже предел.

Пытаются обогнать квадрат для расстояния редактирования в худшем случае. При SETH - бесполезно; выигрыш дают только ограничения на вход (малое расстояние - O(n · d), похожие строки, приближение).

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

Нижние границы экономят время инженера так же, как NP-полнота: прежде чем оптимизировать алгоритм, стоит знать, есть ли куда. Сравнение больших текстов, выравнивание последовательностей в биоинформатике, сравнение версий файлов - квадрат здесь предел, и выигрыш ищут в ограничениях на входы: diff в git работает за O(n · d), где d - размер различий, именно потому, что обычно различий мало.

Теперь сам

1. Сведение переводит 3-SAT с n переменными в граф с n³ вершинами. Какую нижнюю границу даёт ETH?
2. Алгоритм для независимого множества на плоском графе работает за 2^(√n). Совместим ли он с ETH? А за 2^(n^(1/3))?
3. Почему из SETH следует, что расстояние редактирования не считается за n^1,9?