Shen, Alexander
Combinatorial proof of Muchnik's theorem
Abstract
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
@InProceedings{shen:DSP:2006:625,
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 = {http://drops.dagstuhl.de/opus/volltexte/2006/625},
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 |
31.07.2006
