Комбинаторные методы в теории колмогоровской сложности с ограничением на ресурсы

• Автор: Мусатов, Даниил Владимирович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 128 с. : ил.

Оглавление
1 Введение
1.1 Актуальность темы и цели работы
1.2 Основные результаты
1.3 Апробация работы
1.4 План дальнейшего изложения
1.5 Используемые обозначения
Благодарности
2 Обзор основных понятий
2.1 Колмогоровская сложность
2.2 Экстракторы
2.3 Колмогоровские экстракторы
2.4 Схемы из функциональных элементов
2.5 Генераторы псевдослучайных чисел
2.6 Вычислительная ХОБ-Лемма
2.7 Отдельные используемые неравенства
3 Применение экстракторов для доказательства теоремы
Мучника об условной сложности
3.1 Формулировка теоремы и идея доказательства
3.2 Применение экстракторов для доказательства теоремы
3.3 Теорема Мучника для нескольких условий и префиксные экстракторы

4 Теорема Мучника для сложности с ограничением на память
4.1 Доказательство при помощи явного экстрактора
4.2 Доказательство при помощи генератора Нисана-Вигдерсона
4.2.1 Формулировка нужного свойства и доказательство существования
4.2.2 Распознавание малого числа коллизий при помощи схемы константной глубины
4.2.3 Поиск аргумента генератора Нисана-Вигдерсона, порождающего функцию с малым числом коллизий
4.2.4 Формулировка и доказательство варианта теоремы Мучника
4.3 Теорема с ограничением на память для нескольких условий
4.3.1 Доказательство при помощи явного экстрактора
4.3.2 Доказательство при помощи генератора Нисана-Вигдерсона
4.3.3 Компиляция двух подходов и теорема для полиномиального числа условий
5 Теорема Мучника для САМ-сложности с ограничением на время
5.1 Формулировка теоремы
5.2 Описание конструкции
5.3 Доказательство корректности конструкции
5.4 О теореме для нескольких условий
6 Колмогоровские экстракторы с ограничением на память
6.1 Определения и формулировки теорем
6.2 Пёстрые таблицы
6.3 Идея доказательства основной теоремы
6.4 Применение генератора Нисана-Вигдерсона
6.5 Завершение доказательства основной теоремы
6.6 Теорема для малых ограничений на память
Заключение
Литература

Глава 1 Введение
1.1 Актуальность темы и цели работы
Понятие колмогоровской сложности появилось в 1960-х годах в работах Колмогорова [6], Соломонова [45| и Чейтина [14; 15]. Колмогоровскую сложность можно определять для любых конечных объектов, но достаточно рассматривать двоичные слова, т.е. конечные последовательности из нулей и единиц. Неформально говоря, сложность слова есть сложность его алгоритмического описания, т.е. длина кратчайшей программы, которая печатает это слово на пустом входе. Также рассматривают условную сложность одного слова относительно другого, т.е. длину кратчайшей программы, печатающей первое слово после получения на вход второго. Разумеется, эти определения зависят от того, какой язык программирования используется для описания, но согласно теореме Колмогорова-Соломонова существует оптимальный язык программирования, при котором сложности всех слов минимальны с точностью до аддитивной константы. Это позволяет не ссылаться на конкретный язык программирования и при этом формулировать различные утверждения о связи сложностей различных слов. Эти утверждения формулируются с точностью до аддитивной константы, зависящей только от выбора оптимального языка программирования и не зависящей от конкретных слов. В формулировках эта константа традиционно обозначается через 0(1). (Некоторые утверждения формулируются с точностью до другого аддитивного слагаемого: 0(logn), 0(log3n) и т.п.) К сожалению, до сих пор не сложилось единого обозначения для сложности. В диссертации сложность слова х обозначается через С(х), а условная сложность слова х относительно у — через С(я:|2/)-
Также рассматривают колмогоровскую сложность с ограничением на ре-

3. Можно отбросить последние О(к^п) битов программы р и дописать их к О(к^п) битам, задающим а при известных р и Ь. Таким образом, первое неравенство останется в силе. Третье неравенство при этом тоже сохранится. В итоге мы получим следующую эквивалентную формулировку: для любых двоичных слов а иЪ существует строка р длины не больше С(а|6). такая что С(а|р, Ь) ^ 0(к^С(а)) и С(р|а) ^ 0(к^С(а)).
4. Можно, наоборот, добиться выполнения условия С(ар, Ь) ^ 0(1)- Для этого нужно включить 0(ogn) битов, описывающих а при известных р и Ъ в исходной формулировке, в состав программы р и в состав описания р при известном а. При этом, разумеется, длину р уже нельзя будет уменьшить до к, а константа в оценке С(р|а) возрастёт.
5. По причинам, указанным в первом замечании, достаточно доказать теорему для случая, когда не только сложность, но и длина а меньше п: замена слова а на его кратчайшее описание изменяет все сложности, содержащие а, не более, чем на 0(logn).
Общий метод доказательства естественным образом вытекает из формулировки. Неравенство С(р|а) < 0{о^п) означает, что слову а каким-то вычислимым образом сопоставлены 2°(1о8П) — ро1у(п) слов (будем называть из образами а), среди которых нужно выбрать р. Неравенство С(р) ^ к + 0(1о§п) означает, что каждое из этих слов имеет сложность (или длину) не больше к + О(к^га). Задача состоит в построении такой конструкции, чтобы хотя бы для одного из слов р было выполнено неравенство С(ар, Ь) ^ 0(logn). Естественный способ этого добиться таков: заметим, что при известном Ь можно перечислять элементы множества в/, = {ж | С(ж|6) < к}. В этом множестве заведомо лежит а. Кроме того, можно перечислять элементы £&, которым сопоставлено слово р (т.е. прообразы р): слово а также лежит среди них. Если таких элвхментов полиномиальное количество, то слово а может быть задано своим номером среди них. Таким образом, требуется, чтобы хотя бы у одного образа а было полиномиальное число прообразов внутри Бь-
Мы получили, что для доказательства теоремы Мучника достаточно доказать существование функции /: {0,1}<7г х {0,1}'г —> {0,1}*, где д = О(к^п), со следующим свойством: для всех двоичных слов а и 6, таких