Time-bounded Kolmogorov complexity and Solovay functions

DOI10.1007/s00224-012-9413-4zbMath1261.68077OpenAlexW2048167699MaRDI QIDQ1946499

Thorsten Kräling, Wolfgang Merkle, Rupert Hölzl

Publication date: 15 April 2013

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-012-9413-4

zbMATH Keywords

Kolmogorov complexitytraceabilitycomputational depthhigh degreeKummer's gap theoremSolovay function

Mathematics Subject Classification ID

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

Related Items

Lowness and logical depth, CHAITIN’S Ω AS A CONTINUOUS FUNCTION, Solovay functions and their applications in algorithmic randomness, Searching for shortest and least programs

Cites Work

• Unnamed Item
• Unnamed Item
• Strong jump-traceability. II: \(K\)-triviality
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• Computational depth and reducibility
• Process complexity and effective random tests
• Strong jump-traceability. I: The computably enumerable case
• Randomness and Recursive Enumerability
• Algorithmic Randomness and Complexity
• Time-Bounded Kolmogorov Complexity and Solovay Functions
• 𝐾-trivial degrees and the jump-traceability hierarchy
• Kolmogorov Complexity and Solovay Functions
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• An introduction to Kolmogorov complexity and its applications