When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06051.5
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 =	{Shen, Alexander},
  title =	{{Combinatorial proof of Muchnik's theorem}},
  booktitle =	{Kolmogorov Complexity and Applications},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6051},
  editor =	{Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-6258},
  doi =		{10.4230/DagSemProc.06051.5},
  annote =	{Keywords: Matching conditional descriptions Kolmogorov complexity}

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI