Применения леммы Ловаса

• Гарантированная выполнимость кнф
  • Достаточно: каждое условие на $n$ переменных и имеет не более $N=2^n/4$ соседей (с общими переменными). Видно, что $2^n/4$ нельзя заменить на $2^n$
  • подбор $\varepsilon$: надо $2^{-n}<\varepsilon (1-\varepsilon)^{N}$, максимум достигается, когда $\varepsilon=1/(N+1)$, то есть $N\approx 2^n/e$
• Возможность заполнения двумерной таблицы, если на каждом ребре запрещён $1\%$ пар. (Уже непонятно, как без леммы Ловаса)
• Отступление: переход от заполнения сколь угодно большой таблицы к заполнению бесконечной (компактность, лемма Кёнига, теорема Гёделя о полноте)
• Почему это рассуждение не эффективизируется: пример бесконечного разрешимого поддерева полного двоичного дерева без вычислимой бесконечной ветви
• Двоичные слова без (достаточно длинных квадратов). Обобщение: задача о запрещённых подсловах, если запрещено $F_k$ слов длины $k$, при этом $F_k<2^{\alpha k}$ при $\alpha<1$, то есть бесконечная последовательность без длинных запрещённых подслов
• Суперслучайная и потому неслучайная последовательность с несжимаемыми подсловами
• Проверка выполнения леммы: $\varepsilon_k=2^{-\beta k}$ для слов длины $k$ (выбор константы: $\alpha<\beta<1$)

Ещё о запрещённых подсловах

• Метод потенциала по Миллеру
  • Идея: насколько мы близки к краю
  • Число запрещённых вхождений в уже построенный участок, но учитываем также и возможные вхождения, пересекающие уже построенный участок (в виде математического ожидания: если не хватает $s$ букв, то с весом $2^{-s}$. Обозначаем $D(x)$ и получаем формулу: $$D(x)+\sum_k F_k /2^k=\tfrac{1}{2}D(x0)+\tfrac{1}{2}D(x1)$$ (левая часть учитывает ещё и матожидание сразу справа от конца $x$)
  • чисто формально можно подсчитывать вхождения, пересекающиеся с $x$, но выходящие за пределы $x$ на $k$ букв, с весом $c^{-k}$. Если слово $x$ не содержит запрещённых вхождений, то верно аналогичное равенство: $$D(x)+\sum_k F_k c^k=c D(x0)+ c D(x1)$$ Мы хотим поддерживать $D(x)<1$, увеличивая $x$ (заметим, что в этом случае нет вхождений в $x$, так что можно применить равенство --- это сработает, если $$1+\sum\k F_k c^k < 2c,$$ то есть если $$\sum_k F_k c^k < 2c-1$$ при некотором положительном $c$ (больше $1/2$, иначе правая часть отрицательна)
  • Даёт вычислимую ветвь, если множество $F_k$ разрешимо и ряд вычислимо сходится. (чего можно добиться, немного уменьшив $c$ без нарушения условия)
• Рассуждение со сжатием (вариант алгоритма Мозера для данного конкретного случая).
  • Процесс: добавляем случайные биты, когда появляется запрещённое слово, оно пропадает (<<тетрис>>-алгоритм, только игрок лишь наблюдает); удаляется только одно слово (второе удалилось бы раньше)
  • Протокол: на каждом шаге записываем, что произошло. Два варианта: либо просто добавление бита (и тогда мы не записываем, какой бит добавили), либо добавление бита со схлопыванием слова (и тогда записываем, какое слово)
  • Надо доказать,что длина текущего слова не может оставаться ограниченной (точнее, что вероятность этого мала)
  • Наблюдение: по протоколу и тому, какие биты остались на данный момент, можно восстановить все использованные случайные биты (обратный ход)
  • Если мы научимся кодировать протокол экономно (меньше одного бита на операцию), то видно, что биты будут накапливаться (иначе оставалось бы ограниченное количество битов, а протокол кодируется короче, чем случайная последовательность)
  • Для протокола используется арифметическое кодирование: добавление без схлопывание имеет вес $p_0$, добавление со схлопыванием слова длины $k$ имеет вес $p_k/F_k$ (все слова поровну и $p_k$ на всех)
  • Мы выбираем $p_0>1/2$, тогда на добавление уходит меньше $1$ бита, и можно оставлять (для амортизационного анализа) запас $z>0$, который затем можно расходовать на кодирование схлопывания (без этого там не обойтись: схлопываться могут самые разные слова)
  • Необходимые неравенства: $$\log (1/p_0)\le 1-z;$$ $$\log(1/p_k)+\log F_k \le 1+z(k-1);$$ $$\sum_k p_k<1$$ (строгое неравенство в последнем случае создаёт необходимый запас)
  • можно считать, что в первых двух случаях равенства, и получится как раз условие Миллера

Выполнимость $n$-кнф с $2^{n-3}$ соседей у каждого клоза

• алгоритм: поочерёдное исправление всех клозов, если они не выполнены;
• исправление одного клоза (известно, что он не выполнен): перерандомизация плюс рекурсивный вызов для всех соседей (если к моменту вызова клоз выполнен, он пропускается);
• достаточно доказать, что исправление кончается за полиномиальное время (с вероятностью почти $1$);
• случайные биты в процессе исправления одного клоза можно восстановить по последовательности вызовов и по текущим битам (обратный ход);
• последовательность вызовов --- обход дерева рекурсии, каждый шаг записываем битами: вверх или вниз, если вверх, то по какой ветви ($n-3$ битов), ещё один бит надо запасти для амортизационного анализа на выполнение шага вниз, получается $n-1$ на вызов вместо $n$, так что долго так быть не может

Общий алгоритм Мозера--Тардоша и его оценка

• Собственно алгоритм: выбор нарушенного условия по какому-то правилу и его перерандомизация
• Утверждение: если выполнено условие леммы Ловаса, то математическое ожидание количества исправлений $i$-го условия не больше $\varepsilon_i/(1-\varepsilon_i)$
• Деревья зависимостей и их свойства
• Оценка вероятности появления данного дерева (запасённые переменные)
• Сравнение с вероятностью в процессе Гальтона--Уотсона и окончание доказательства

Вероятностные алгоритмы для бесконечных задач

• Массовые проблемы, сводимость
• Вероятностно разрешимые массовые проблемы (в сильном и слабом смысле)
• Получение невычислимой последовательности (разрешимая проблема)
• Получение конкретной невычислимой последовательности: теорема Мура--де Леу--Шеннона--Шапиро: доказательство с теоремой Лебега о плотности
• Выходные меры вероятностных алгоритмов: описание. Доказательство с полумерой
• Отступление: максимальная полумера, неслучайные последовательности и почему они имеют меру нуль
• Задача о фейерверках
• Слабая разрешимость о построении последовательности натуральных чисел, не мажорируемой никакой тотальной вычислимой функцией

Машины с переписыванием ответа

• Определение, эквивалентность покоординатному
• Для одного бита: вычислимые точки в пространстве измеримых множеств
• Если такая машина даёт элемент замкнутого множества с положительной вероятностью, то это замкнутое множество имеет вычислимую точку
• Бесконечный вариант задачи о запрещённых словах и прямоугольниках