Laboratory of Mathematical Logic at PDMI

Пятница, 17 февраля, ауд. 106. Начало в 18:00.

Докладчик: Даниил Мусатов (МГУ).

Тема: Наивная дерандомизация для колмогоровской сложности с ограничением на память.

Abstract

Многие теоремы о колмогоровской сложности доказываются по следующей схеме: определяется комбинаторный объект с некоторыми свойствами, затем вероятностным методом доказывается его существование, из всех таких объектов выбирается наиболее простой (т.е. первый в некотором естественном порядке перебора, его сложность будет логарифмической), который используется в доказательстве теоремы. Для сложности с ограничением на ресурсы такая схема не проходит: поиск нужного объекта требует слишком много времени и памяти. Однако, во многих случаях может помочь "наивная" дерандомизация: докажем выполнение нужного свойства не только для случайного объекта, но и для псевдослучайного, а потом найдём нужный объект среди порождённых псевдослучайным генератором.

В докладе при помощи этой техники будет доказана версия теоремы Мучника для сложности с полиномиальным ограничением на память. Теорема состоит в следующем: для любых слов a и b существует программа p, переводящая a в b, имеющая наименьшую возможную длину и простая относительно b. Все сложности меряются с точностью до аддитивного логарифмического слагаемого. Благодаря совету Ронена Шалтиела доказательство будет упрощено по сравнению с рассказанным на CSR 2011.

Никаких предварительных знаний не требуется. Все необходимые определения будут даны в докладе.