Введение
1 Введение 4
1.1 Актуальность темы и цели работы 4
1.2 Основные результаты 8
1.3 Апробация работы 9
1.4 План дальнейшего изложения 9
1.5 Используемые обозначения 11
Благодарности 13
2 Обзор основных понятий 14
2.1 Колмогоровская сложность 14
2.2 Экстракторы 18
2.3 Колмогоровские экстракторы 24
2.4 Схемы из функциональных элементов 26
2.5 Генераторы псевдослучайных чисел 27
2.6 Вычислительная XOR-Лемма 29
2.7 Отдельные используемые неравенства 30
3 Применение экстракторов для доказательства теоремы Мучника об условной сложности 32
3.1 Формулировка теоремы и идея доказательства 33
3.2 Применение экстракторов для доказательства теоремы 37
3.3 Теорема Мучника для нескольких условий и префиксные экстракторы 41
4 Теорема Мучника для сложности с ограничением на память 48 48
4.2 Доказательство при помощи генератора Нисана-Вигдерсона 4.2.1 Формулировка нужного свойства и доказательство существования 56
4.2.2 Распознавание малого числа коллизий при помощи схемы константной глубины 57
4.2.3 Поиск аргумента генератора Нисана-Вигдерсона, порождающего функцию с малым числом коллизий 59
4.2.4 Формулировка и доказательство варианта теоремы Мучника 62
4.3 Теорема с ограничением на память для нескольких условий 64
4.3.1 Доказательство при помощи явного экстрактора 64
4.3.2 Доказательство при помощи генератора Нисана-Вигдерсона 68
4.3.3 Компиляция двух подходов и теорема для полиномиального числа условий 71
5 Теорема Мучника для САМ-сложности с ограничением на время 77
5.1 Формулировка теоремы 77
5.2 Описание конструкции 78
5.3 Доказательство корректности конструкции 82
5.4 О теореме для нескольких условий 90
6 Колмогоровские экстракторы с ограничением на память 93
6.1 Определения и формулировки теорем 93
6.2 Пёстрые таблицы 94
6.3 Идея доказательства основной теоремы 100
6.4 Применение генератора Нисана-Вигдерсона 102
6.5 Завершение доказательства основной теоремы 111
6.6 Теорема для малых ограничений на память 118
Заключение 120
Литература
