Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Лемма Ловаса и другие вероятностные доказательства существования
Санкт-Петербург / весна 2015, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

Бывают ситуации, когда существование объекта с какими-то свойствами доказать легко, но это доказательство неконструктивно (не даёт возможности предъявить такой объект). Например, можно установить, что число всех объектов определённого вида, не обладающих нужным свойством, меньше числа всех объектов этого вида. Это можно переформулировать в терминах вероятности, а также в терминах сложности описания (плохие объекты можно коротко описать, поэтому их мало). Мы рассмотрим простые примеры такого рода, а также более сложную вероятностную технику, называемую "леммой Ловаса", а также вероятностный алгоритм построения объектов, придуманный Мозером и модифицированный Тардошем, и его следствия (слова без запрещённых подслов и другие применения).

Задачи Вопросы по рассказанному и решения этих задач можно посылать по адресу sasha.shen@gmail.com — информацию о решённых задачах я перешлю в computer science center. (Предупреждение: несколько последних задач я решать не умею и потому особенно заинтересован в их решениях.)

  1. Докажите, что если множество \(A\) натуральных чисел неразрешимо, то вероятность события ``\(A\) сводится по Тьюрингу к случайной последовательности битов'' (т.е. существует машина с оракулом, которая разрешает \(A\), если использовать эту последовательность как оракул) равна \(0\).
  2. Пусть мы хотим применить критерий Миллера и других к построению последовательности в двоичном алфавите, не содержащей кубов слов длины \(n\) (это длина слова, куб имеет длину \(3n\)) и больше. При каких \(n\) это удастся сделать?
  3. Докажите, что если для каждого \(k\) алгоритмически указан список из не более чем \(2^{0.99k}\) слов длины \(k\), то можно найти число \(N\) и вычислимую двустороннюю последовательность, в которой нет запрещённых слов длины \(N\) и более.
  4. Докажите, что если у степенного ряда для \(\frac{1}{1-2x+F_2x^2+F_3x^3+\ldots},\) где \(F_2,F_3,\ldots\) --- количества запрещённых слов длин \(2,3,\ldots\) (запрещённых слов меньших длин нет) все коэффициенты положительны, то существуют сколь угодно длинные слова без запрещённых подслов.
  5. (Продолжение) Можно ли как-то связать предыдущий критерий с критерием Миллера (в знаменателе как раз стоит то самое выражение!)?
  6. Попытаться вывести критерий Миллера (с тем же или более слабым условием) с помощью леммы Ловаса.
  7. Попытаться переформулировать доказательство алгоритма Мозера--Тардоша в общем (или чуть менее общем) случае в терминах сжатия случайных битов.

Ссылки

  1. http://arxiv.org/abs/1305.1535: бесконечная вычислимая лемма Ловаса (и изложение доказательства Мозера--Тардоша в общем случае), а также обсуждение задачи о фейрверках.
  2. http://www.lirmm.fr/~ashen/kolmbook.pdf: книжка по колмогоровской сложности, там есть классической доказательство леммы Ловаса (неконструкструктивное), критерия Миллера, доказательства со сжатием для случая \(n\)-кнф и некоторая общая информация о вероятностных алгоритмах и выходных распределениях.

Дата и время Занятие Место Материалы
28 февраля
17:20–18:55
Вероятностный метод: средние, Лекция ПОМИ РАН видео
28 февраля
19:15–20:50
Вероятностный метод: оценка суммы, Лекция ПОМИ РАН видео
01 марта
11:15–12:50
Вероятностные оценки: метод сжатия, Лекция ПОМИ РАН видео
01 марта
13:00–14:35
Ещё о вероятностных доказательствах, Лекция ПОМИ РАН видео
01 марта
15:35–17:10
Дерандомизация, Лекция ПОМИ РАН видео
07 марта
17:20–18:55
Лемма Ловаса: формулировка, Лекция ПОМИ РАН видео
07 марта
19:15–20:50
Доказательство леммы Ловаса, Лекция ПОМИ РАН видео
08 марта
11:15–12:50
Применения леммы Ловаса, ещё о запрещённых подсловах, выполнимость n-кнф с 2n−3 соседей у каждого клоза, Лекция ПОМИ РАН видео
08 марта
13:00–14:35
Общий алгоритм Мозера-Тардоша и его оценка, Лекция ПОМИ РАН видео
08 марта
15:35–17:10
Вероятностные алгоритмы для бесконечных задач, машины с переписыванием ответа, Лекция ПОМИ РАН видео