Extractors and an efficient variant of Muchnik's theorem

Details Extractors and an efficient variant of Muchnik's theorem Extractors and an efficient variant of Muchnik's theorem

2008-11-24

arxiv.org/abs/0811.3958v1

Computer Science

Computational Complexity

37 pages, in Russian

Scientific paper

Muchnik's theorem about simple conditional descriprion states that for all words $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$. This paper presents a new proof of this theorem, based on extractors. Employing the extractor technique, two new versions of Muchnik's theorem for space- and time-bounded Kolmogorov complexity are proven.

Affiliated with

Also associated with

No associations

Rating

Extractors and an efficient variant of Muchnik's 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 Extractors and an efficient variant of Muchnik's theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extractors and an efficient variant of Muchnik's theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-303541