Применения леммы Ловаса
- Гарантированная выполнимость кнф
- Достаточно: каждое условие на $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)$
- Деревья зависимостей и их свойства
- Оценка вероятности появления данного дерева (запасённые переменные)
- Сравнение с вероятностью в процессе Гальтона--Уотсона и окончание доказательства
Вероятностные алгоритмы для бесконечных задач
- Массовые проблемы, сводимость
- Вероятностно разрешимые массовые проблемы (в сильном и слабом смысле)
- Получение невычислимой последовательности (разрешимая проблема)
- Получение конкретной невычислимой последовательности: теорема Мура--де Леу--Шеннона--Шапиро: доказательство с теоремой Лебега о плотности
- Выходные меры вероятностных алгоритмов: описание. Доказательство с полумерой
- Отступление: максимальная полумера, неслучайные последовательности и почему они имеют меру нуль
- Задача о фейерверках
- Слабая разрешимость о построении последовательности натуральных чисел, не мажорируемой никакой тотальной вычислимой функцией
Машины с переписыванием ответа
- Определение, эквивалентность покоординатному
- Для одного бита: вычислимые точки в пространстве измеримых множеств
- Если такая машина даёт элемент замкнутого множества с положительной вероятностью, то это замкнутое множество имеет вычислимую точку
- Бесконечный вариант задачи о запрещённых словах и прямоугольниках