Time-Bounded Kolmogorov Complexity and Solovay Functions

DOI10.1007/978-3-642-03816-7_34zbMath1250.03068MaRDI QIDQ3182941

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

Publication date: 16 October 2009

Published in: Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03816-7_34

Mathematics Subject Classification ID

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

03D32: Algorithmic randomness and dimension

Related Items

STRONG JUMP-TRACEABILITY, Inherent enumerability of strong jump-traceability, A \(K\)-trivial set which is not jump traceable at certain orders, Kolmogorov complexity of initial segments of sequences and arithmetical definability, Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega, Time-bounded Kolmogorov complexity and Solovay functions, Random Semicomputable Reals Revisited, Randomness, Computation and Mathematics

Cites Work

• Unnamed Item
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• Computational depth and reducibility
• Randomness and Recursive Enumerability
• Algorithmic Randomness and Complexity
• 𝐾-trivial degrees and the jump-traceability hierarchy
• Computability and Randomness
• Kolmogorov Complexity and Solovay Functions
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• An introduction to Kolmogorov complexity and its applications