Combinatorial proof of Muchnik's theorem

Author Alexander Shen



PDF
Thumbnail PDF

File

DagSemProc.06051.5.pdf
  • Filesize: 150 kB
  • 5 pages

Document Identifiers

Author Details

Alexander Shen

Cite AsGet BibTex

Alexander Shen. Combinatorial proof of Muchnik's theorem. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
https://doi.org/10.4230/DagSemProc.06051.5

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.
Keywords
  • Matching conditional descriptions Kolmogorov complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail