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