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

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