Локальная лемма Ловаса: редкие конфликты и локальное исправление

Если строишь граф зависимостей и отличаешь существование от алгоритма, листай до «Теперь сам».

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

Ты случайно выбрал значения логических переменных. Несколько условий нарушены. Можно выбросить всю попытку и начать с нуля, но большая часть условий зависит от других переменных и уже выполнена. Возможно ли исправлять конфликты локально, не разрушая весь достигнутый результат? Лемма объясняет, когда разреженные зависимости позволяют такое поведение обосновать.

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

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

Механизм: вероятности недостаточно без карты зависимости

Для независимых переменных каждому плохому событию сопоставляем набор переменных, от которых оно зависит. Соединяем два события, если их наборы пересекаются. Несмежное событие независимо не только от каждого другого по отдельности, но и от любого набора событий вне его соседства. Это сильнее попарной независимости и необходимо для стандартной формулировки.

В задаче выполнимости k литералов на k различных переменных в дизъюнкции дают вероятность нарушения 2⁻ᵏ при независимых честных битах. Соседние дизъюнкции имеют общую переменную. Поэтому большая формула с локальными пересечениями может удовлетворять e·2⁻ᵏ·(d+1)≤1, даже если сумма вероятностей всех нарушений давно превысила единицу.

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

Правило

Проверь вероятность события, корректный граф зависимостей и максимальную степень, затем применяй достаточное условие. Для локального алгоритма явно задай независимые переменные и их пересэмплирование. Сам факт успешного случайного запуска не доказывает оценку времени.

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

Каждая из четырёх дизъюнкций содержит четыре переменные, одна общая для всех, остальные уникальны. Вероятность нарушения 1/16, число соседей d=3. Условие e·4/16<1 выполнено. Код фиксирует зерно только для повторения опыта; определение вероятностей относится к независимым исходам модели, а не к этому единственному зерну.

from math import e
from random import Random

# Литерал: номер переменной и значение, делающее его истинным.
clauses = [
    [(0, True), (1, True), (2, False), (3, True)],
    [(0, False), (4, True), (5, True), (6, False)],
    [(0, True), (7, False), (8, True), (9, True)],
    [(0, False), (10, True), (11, False), (12, True)],
]


def satisfied(clause, values):
    return any(values[v] == truth for v, truth in clause)


def repair(seed):
    rng = Random(seed)
    values = [bool(rng.getrandbits(1)) for _ in range(13)]
    for count in range(10001):
        bad = next((c for c in clauses
                    if not satisfied(c, values)), None)
        if bad is None:
            return count, values
        if count == 10000:
            raise RuntimeError("Ограничитель демонстрации")
        for v, _ in bad:
            values[v] = bool(rng.getrandbits(1))


variables = [{v for v, _ in c} for c in clauses]
degree = max(sum(bool(a & b) for j, b in enumerate(variables)
                 if i != j) for i, a in enumerate(variables))
print("p:", 1/16, "d:", degree)
print("Условие:", f"{e * (degree+1)/16:.6f}")
counts = []
for seed in range(100):
    count, values = repair(seed)
    assert all(satisfied(c, values) for c in clauses)
    counts.append(count)
print("Успешных опытов:", len(counts))
print("Максимум ремонтов в опытах:", max(counts))

p: 0.0625 d: 3
Условие: 0.679570
Успешных опытов: 100
Максимум ремонтов в опытах: 2

Результат проверяется прямым вычислением всех условий после ремонта. Ограничитель числа шагов защищает демонстрацию от зависания и сообщает об отказе опыта; он не является доказанной теоретической границей алгоритма. Нельзя молча выдать частичное присваивание за решение при достижении ограничителя.

Разбор: условие не необходимо

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

Похожая ошибка - считать только фактически нарушенные события при вычислении d. Граф задаёт потенциальное влияние при любых значениях переменных. Сегодня выполненное условие завтра может стать нарушенным после ремонта соседа.

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

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

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

Нужна конструкция комбинаторного объекта со множеством локальных запретов: раскраска, расписание, присваивание. Глобальная вероятность ошибки по объединению может ничего не говорить. Разреженный граф зависимостей позволяет доказать существование и обосновать локальную починку, сохраняя ту часть объекта, которой конфликт не касается.

Теперь сам

Для k=4 и d=3 посчитай левую часть условия. А если степень выросла до 10, можно ли заключить, что формула невыполнима?