City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Применения леммы Ловаса, ещё о запрещённых подсловах, выполнимость n-кнф с 2n−3 соседей у каждого клоза
Lovasz local lemma and probabilistic method

What: Lecture
When: Sunday, 08 March 2015, 11:15–12:50
Where: ПОМИ РАН

Description

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

  • Гарантированная выполнимость кнф
    • Достаточно: каждое условие на $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)$
  • Деревья зависимостей и их свойства
  • Оценка вероятности появления данного дерева (запасённые переменные)
  • Сравнение с вероятностью в процессе Гальтона--Уотсона и окончание доказательства

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

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

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

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

Video