PCP и карта границ: где простые алгоритмы оказались лучшими возможными

Если ты знаешь, что утверждает теорема PCP, почему 7/8 для MAX-3SAT нельзя улучшить и почему у покрытия множествами нет постоянного множителя, а у вершинного покрытия вопрос открыт, листай до «Теперь сам».

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

В главе об округлении монетка выполняла скобку из трёх литералов с вероятностью 7/8. Простейший алгоритм, который вообще не смотрит на формулу. Для формул, где в каждой скобке три литерала трёх разных переменных, он в среднем выполняет 7/8 скобок - а значит, не меньше 7/8 оптимума; метод условных ожиданий превращает это среднее в гарантию.

Ответь себе до чтения: неужели нельзя лучше? Есть релаксации, есть полуопределённое программирование, которое для скобок из двух литералов даёт 0,94. Ответ - нельзя: для каждой ε > 0 получить 7/8 + ε NP-трудно (Хостад, 2001). Монетка, которая не читает формулу, - лучший возможный полиномиальный алгоритм (для случайных алгоритмов - при чуть более сильном предположении, чем P ≠ NP). Чтобы доказать такое, обычной пропасти мало: её надо выточить до 7/8, и для этого нужна теорема PCP.

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

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

Отсюда пропасти: «есть доказательство» становится «все проверки проходят», а «нет доказательства» - «заметная доля проверок проваливается». Между «все» и «заметная доля» - разрыв, а это и есть то, что запрещает хорошие приближения.

Механизм: от проверки к пропасти

Теорема PCP (Арора, Лунд, Мотвани, Судан, Шеги, Сафра, 1992-1998; комбинаторное доказательство - Динур, 2007). Для любой задачи из NP есть проверяющий, который берёт O(log n) случайных бит, читает в предъявленном доказательстве постоянное число символов и: на верном утверждении при правильном доказательстве принимает всегда; на неверном отклоняет с вероятностью хотя бы 1/2 при любом доказательстве.

Пропасть для MAX-3SAT. Каждую проверку (несколько прочитанных символов) записывают несколькими скобками из трёх литералов. Верное утверждение - выполнимы все скобки. Неверное - проваливается постоянная доля проверок, а значит, ложна постоянная доля скобок. Разрыв «все» против «не больше (1 − δ)» - и MAX-3SAT не имеет PTAS. Хостад довёл конструкцию до предела: «выполнима» против «не больше 7/8 + ε».

Где проходят границы сейчас:

задача                   алгоритм              нельзя лучше (P ≠ NP)
MAX-3SAT, по 3 в скобке  7/8 (монетка)         7/8 + ε   (Хостад, 2001)
покрытие множествами     H(n) ≈ ln n (жадно)   (1 − ε)·ln n
                                               (Динур, Штойрер, 2014)
k-центр                  2                     2 − ε
вершинное покрытие       2                     1,36 (Динур, Сафра, 2005)
                                               √2 − ε (Кхот, Минцер,
                                                       Сафра, 2018)
метрический коммивояжёр  1,5 − 10⁻³⁶           123/122
                                               (Карпински и др., 2015)
упаковка в контейнеры    3/2                   3/2 − ε

У вершинного покрытия разрыв между 2 и √2 открыт: если верна гипотеза об уникальных играх (Кхот, 2002), лучше двойки нельзя. У коммивояжёра разрыв между 1,5 и 1,008 - один из самых известных открытых вопросов области.

Правило

Теорема PCP: доказательство из NP можно проверить, прочитав постоянное число случайных символов, - и из неё следуют тонкие пределы приближения. Для MAX-3SAT случайный набор с его 7/8 оптимален; для покрытия множествами жадность с H(n) ≈ ln n оптимальна с точностью до 1 − ε, и постоянного множителя нет. Для вершинного покрытия и метрического коммивояжёра между известным алгоритмом и известным пределом остаётся разрыв.

Разбор: 7/8 на настоящих формулах

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

import random

def vypolneno(formula, nabor):
    s = 0
    for skobka in formula:
        ok = False
        for lit in skobka:
            if (lit > 0) == nabor[abs(lit)]:
                ok = True
        if ok:
            s = s + 1
    return s

def vse_nabory(n):
    nabory = []
    for kod in range(2 ** n):
        nabor = [False]
        for i in range(n):
            nabor.append(kod >> i & 1 == 1)
        nabory.append(nabor)
    return nabory

vosem = []
for a in [1, -1]:
    for b in [2, -2]:
        for c in [3, -3]:
            vosem.append([a, b, c])
schet = []
for nabor in vse_nabory(3):
    schet.append(vypolneno(vosem, nabor))
print(len(vosem), schet)

random.seed(3)
n = 8
formula = []
for i in range(34):
    peremennye = []
    while len(peremennye) < 3:
        v = random.randint(1, n)
        if v not in peremennye:
            peremennye.append(v)
    skobka = []
    for v in peremennye:
        skobka.append(random.choice([v, -v]))
    formula.append(skobka)
vsego = 0
luchshee = 0
for nabor in vse_nabory(n):
    k = vypolneno(formula, nabor)
    vsego = vsego + k
    luchshee = max(luchshee, k)
print(vsego / 2 ** n, 7 / 8 * 34, luchshee)

8 [7, 7, 7, 7, 7, 7, 7, 7]
29.75 29.75 33

Восемь скобок на трёх переменных: любой набор выполняет ровно семь - ту единственную скобку, которая состоит из противоположных литералов, он нарушает. Здесь оптимум равен 7/8 от числа скобок, и монетка, давая 7/8 в среднем, не хуже никакого алгоритма.

Случайная формула: среднее по всем 256 наборам - ровно 29,75 = 7/8 · 34. Это не совпадение, а линейность ожидания: каждая скобка выполняется в 7/8 наборов. Лучший набор выполняет 33. Теорема Хостада говорит, что отличить формулы, где лучший выполняет все скобки, от формул, где лучший выполняет не больше (7/8 + ε), так же трудно, как любую задачу из NP.

Разбор: жадность и логарифм

Для покрытия множествами в главе о жадных алгоритмах была гарантия H(n) = 1 + 1/2 + … + 1/n. Предел - (1 − ε) · ln n. Насколько они близки?

import math

for n in [10, 100, 1000, 10000]:
    h = 0
    for i in range(1, n + 1):
        h = h + 1 / i
    ln = math.log(n)
    print(n, round(h, 3), round(ln, 3), round(h - ln, 3))

10 2.929 2.303 0.626
100 5.187 4.605 0.582
1000 7.485 6.908 0.578
10000 9.788 9.21 0.577

H(n) − ln n сходится к 0,577… - постоянной Эйлера. Гарантия жадности - логарифм плюс константа, предел - логарифм минус сколь угодно малая доля. На ста тысячах элементов это 12,1 против 11,5: жадность из главы о жадных алгоритмах - лучший возможный полиномиальный алгоритм с точностью до процентов.

И отсюда честный ответ на вопрос «есть ли у покрытия множествами постоянный множитель»: нет. ln n растёт без ограничения, и любое c с ростом n окажется меньше (1 − ε) · ln n. Доказательство - сведение с пропастью от задачи «покрытие меток», которая сама выводится из теоремы PCP; Фейге (1998) получил его при чуть более сильном предположении, чем P ≠ NP, а Динур и Штойрер (2014) - при самом P ≠ NP. В курсе это доказательство не воспроизводится: оно занимает десятки страниц.

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

Ищут для MAX-3SAT алгоритм лучше 7/8 в худшем случае. Его нет, если P ≠ NP. На конкретных формулах решатели часто находят оптимум, но гарантию 7/8 + ε не даст никто.

Улучшают жадность для покрытия множествами в поисках гарантии. Гарантия уже предельная. Улучшать стоит константы и практику: чистку, локальный поиск, релаксацию с отсечениями.

Считают границу вершинного покрытия закрытой. Между √2 и 2 - открытый вопрос, и «лучше двойки нельзя» верно только при гипотезе об уникальных играх.

Путают предел приближения с практической точностью. Предел - про худший вход. На реальных входах жадность и решатели часто в процентах от оптимума.

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

Эта таблица - карта, где копать бесполезно. Если задача на работе оказалась MAX-3SAT в одежде (совместимость требований по три), покрытием множествами (минимальный набор поставщиков) или коммивояжёром, известно, какой гарантии ждать от лучшей возможной идеи. Время уходит не на поиск несуществующего алгоритма, а на то, что действительно двигает результат: модель, данные, замер на своих входах.

Теперь сам

1. Сколько скобок из восьми возможных на трёх переменных нарушает набор x₁ = 1, x₂ = 0, x₃ = 1? Какую именно?
2. Почему жадность для покрытия множествами нельзя улучшить до гарантии 0,9 · ln n?
3. У вершинного покрытия алгоритм даёт 2, доказанный предел √2 ≈ 1,414. Что можно сказать про алгоритм с гарантией 1,5?