Improving the Space-Bounded Version of Muchnik's Conditional Complexity Theorem via "Naive" Derandomization

Daniil Musatov

Many theorems about Kolmogorov complexity rely on existence of combinatorial objects with specific properties. Usually the probabilistic method gives such objects with better param…