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:DagSemProc.06051.5,
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 = {https://drops.dagstuhl.de/opus/volltexte/2006/625},
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 |
|
Seminar: |
|
06051 - Kolmogorov Complexity and Applications
|
|
Issue date: |
|
2006 |
|
Date of publication: |
|
31.07.2006 |
31.07.2006
