The Normalized Algorithmic Information Distance Can Not Be Approximated

DOI10.1007/978-3-030-50026-9_9OpenAlexW3037467581MaRDI QIDQ5042235

Bruno Bauwens, Ilya Blinnikov

Publication date: 19 October 2022

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2002.06683

zbMATH Keywords

Kolmogorov complexitycomputability theoryoscillation hierarchyalgorithmic information distance

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Normalized information distance and the oscillation hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• Nonapproximability of the normalized information distance
• Normalized information distance and the oscillation hierarchy
• COMPLEXITY OF COMPLEXITY AND STRINGS WITH MAXIMAL PLAIN AND PREFIX KOLMOGOROV COMPLEXITY
• Kolmogorov Complexity and Algorithmic Randomness
• Information distance
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: The Normalized Algorithmic Information Distance Can Not Be Approximated