Abstract:
An. Muchnik's theorem (2002) states that among all programs that
output $a$ on input $b$ and have length close to optimal there exists
one that is simple conditional on $a$. Moreover, for a polynomial set
$b_1$,...,$b_m$ there exists a string $p$ that is simple conditional
on $a$ and such that its $K(a|b_i)$-bit prefix describes $a$
conditional on $b_i$. It would be shown that for space-bounded
complexity an analogous theorem holds not only for a polynomial set of
$b_i$ but for all strings $b$ of polynomial length. The proof employs
the "naive derandomization" technique: a random object with some
combinatorial properties is replaced by a pseudo-random one obtained
by Nisan-Wigderson pseudo-random generator.
|
