Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization
From MaRDI portal
(Redirected from Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization)
Publication:2254499
Publication:2254499
DOI10.1007/s00224-012-9432-1zbMath1319.68117arXiv1009.5108MaRDI QIDQ2254499
Publication date: 5 February 2015
Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1009.5108
extractors; derandomisation; Muchnik's theorem; Nisan-Wigderson generators; space-bounded Kolmogorov complexity
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)