Non-reducible descriptions for conditional Kolmogorov complexity

DOI10.1016/j.tcs.2007.05.019zbMath1124.68049OpenAlexW2475839174WikidataQ57349757 ScholiaQ57349757MaRDI QIDQ2382285

Michael V. Vyugin, Mikhail Ustinov, Alexander Shen, Andrej A. Muchnik, Nikolai K. Vereshchagin

Publication date: 28 September 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.05.019

zbMATH Keywords

conditional descriptionsConditional Kolmogorov complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items

Nonreducible descriptions for the conditional Kolmogorov complexity

Cites Work

• Nonreducible descriptions for the conditional Kolmogorov complexity
• Theory and Applications of Models of Computation
• Conditional complexity and codes
• Unnamed Item