The Normalized Algorithmic Information Distance Can Not Be Approximated

DOI10.1007/978-3-030-50026-9_9MaRDI QIDQ5042235zbMATH OpenOpenAlexFDO

Authors B. 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)

Cites work

• scientific article; zbMATH DE number 3492569 (Why is no real title available?)
• scientific article; zbMATH DE number 7650931 (Why is no real title available?)
• An introduction to Kolmogorov complexity and its applications
• Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity
• Information distance
• Kolmogorov Complexity and Algorithmic Randomness
• Nonapproximability of the normalized information distance
• Normalized information distance and the oscillation hierarchy

Cited in

(2)

• Normalized information distance and the oscillation hierarchy
• The normalized algorithmic information distance can not be approximated

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5042235)