RUS  ENG
Полная версия
СЕМИНАРЫ

Колмогоровский семинар по сложности вычислений и сложности определений
10 декабря 2012 г. 16:45, г. Москва, Главное здание МГУ, ауд. 16-04


Теорема об универсальном условном кодировании с ограничением на память

Д. В. Мусатов

Аннотация: Теорема Ан.Мучника об условном кодировании (2002) утверждает, что среди всех программ, печатающих $a$ на входе $b$ и имеющих длину, близкую к оптимальной, найдётся программа, простая относительно $a$. Более того, для полиномиального набора слов $b_1$,...,$b_m$ найдётся слово $p$, простое относительно $a$, и такое что его префикс длины $K(a|b_i)$ является описанием $a$ относительно $b_i$. В докладе будет доказано, что для сложности с ограничением на память аналогичная теорема верна не только для полиномиального числа слов $b_i$, но и для всех слов $b$ полиномиальной длины. Доказательство использует технику "наивной дерандомизации": случайный объект с некоторыми комбинаторными свойствами заменяется на псевдослучайный, полученный генератором Нисана-Вигдерсона.


© МИАН, 2024