Time-Bounded Kolmogorov Complexity and Solovay Functions

DOI10.1007/978-3-642-03816-7_34zbMath1250.03068OpenAlexW2110700919MaRDI 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

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32)

Related Items (8)

Random Semicomputable Reals Revisited ⋮ Randomness, Computation and Mathematics ⋮ STRONG JUMP-TRACEABILITY ⋮ Time-bounded Kolmogorov complexity and Solovay functions ⋮ 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 ⋮ Inherent enumerability of strong jump-traceability

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

This page was built for publication: Time-Bounded Kolmogorov Complexity and Solovay Functions