Computer Science – Computational Complexity
Scientific paper
2010-09-26
Computer Science
Computational Complexity
14 pages. Presented at CSR'2011, Yandex Best Student Paper Award
Scientific paper
Many theorems about Kolmogorov complexity rely on existence of combinatorial objects with specific properties. Usually the probabilistic method gives such objects with better parameters than explicit constructions do. But the probabilistic method does not give "effective" variants of such theorems, i.e. variants for resource-bounded Kolmogorov complexity. We show that a "naive derandomization" approach of replacing these objects by the output of Nisan-Wigderson pseudo-random generator may give polynomial-space variants of such theorems. Specifically, we improve the preceding polynomial-space analogue of Muchnik's conditional complexity theorem. I.e., for all $a$ and $b$ there exists a program $p$ of least possible length that transforms $a$ to $b$ and is simple conditional on $b$. Here all programs work in polynomial space and all complexities are measured with logarithmic accuracy instead of polylogarithmic one in the previous work.
No associations
LandOfFree
Improving the Space-Bounded Version of Muchnik's Conditional Complexity Theorem via "Naive" Derandomization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Improving the Space-Bounded Version of Muchnik's Conditional Complexity Theorem via "Naive" Derandomization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improving the Space-Bounded Version of Muchnik's Conditional Complexity Theorem via "Naive" Derandomization will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-561843