Extractors and an efficient variant of Muchnik's theorem

Simple item page
dc.creatorMusatov, Daniil
dc.date2008-11-24
dc.date.accessioned2026-07-07T10:20:44Z
dc.date.available2026-07-07T10:20:44Z
dc.descriptionMuchnik'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.
dc.description37 pages, in Russian
dc.identifierhttps://arxiv.org/abs/0811.3958
dc.identifierhttp://arxiv.org/abs/0811.3958
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/174949
dc.subjectComputational Complexity
dc.titleExtractors and an efficient variant of Muchnik's theorem
dc.typetext

Files

Collections

arXiv