When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-6258
Go to the corresponding Portal

Shen, Alexander

Combinatorial proof of Muchnik's theorem

06051.ShenAlexander.ExtAbstract.625.pdf (0.1 MB)


Original proof of Muchnik's theorem on conditional descriptions can be modified and split into two parts: 1) we construct a graph that allows large online matchings (main part) 2) we use this graph to prove the theorem The question about online matching could be interesting in itself.

BibTeX - Entry

  author =	{Alexander Shen},
  title =	{Combinatorial proof of Muchnik's theorem},
  booktitle =	{Kolmogorov Complexity and Applications},
  year =	{2006},
  editor =	{Marcus Hutter  and Wolfgang Merkle and Paul M.B. Vitanyi},
  number =	{06051},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{},
  annote =	{Keywords: Matching conditional descriptions Kolmogorov complexity}

Keywords: Matching conditional descriptions Kolmogorov complexity
Seminar: 06051 - Kolmogorov Complexity and Applications
Issue Date: 2006
Date of publication: 31.07.2006

DROPS-Home | Fulltext Search | Imprint Published by LZI