Variations on Muchnik's Conditional Complexity Theorem

Details Variations on Muchnik's Conditional Complexity Theorem Variations on Muchnik's Conditional Complexity Theorem

2009-04-20

arxiv.org/abs/0904.3116v4

Computer Science

Computational Complexity

24 pages, 1 figure, presented at CSR2009

Scientific paper

Muchnik's theorem about simple conditional descriptions states that for all strings $a$ and $b$ there exists a short program $p$ transforming $a$ to $b$ that has the least possible length and is simple conditional on $b$. In this paper we present two new proofs of this theorem. The first one is based on the on-line matching algorithm for bipartite graphs. The second one, based on extractors, can be generalized to prove a version of Muchnik's theorem for space-bounded Kolmogorov complexity.

Affiliated with

Also associated with

No associations

Rating

Variations on Muchnik's Conditional Complexity Theorem 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 Variations on Muchnik's Conditional Complexity Theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Variations on Muchnik's Conditional Complexity Theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-370522