Enumerations of the Kolmogorov function

DOI10.2178/jsl/1146620156zbMath1165.03025OpenAlexW2172281706MaRDI QIDQ5480623

Harry Buhrman, Richard Beigel, Peter A. Fejer, Piotr Grabowski, Leen Torenvliet, Luc Longpré, Andrej A. Muchnik, Frank Stephan, Lance J. Fortnow

Publication date: 3 August 2006

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.634.8756

zbMATH Keywords

enumerationKolmogorov complexityKolmogorov function

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Applications of computability and recursion theory (03D80)

Related Items

Extracting randomness within a subset is hard ⋮ Enumerations including laconic enumerators ⋮ Short lists for shortest descriptions in short time ⋮ The axiomatic power of Kolmogorov complexity ⋮ Short lists with short programs in short time ⋮ Index sets and universal numberings ⋮ Searching for shortest and least programs ⋮ Kolmogorov complexity and the Recursion Theorem ⋮ On Approximate Decidability of Minimal Programs ⋮ Cone avoiding closed sets

Cites Work

• Unnamed Item
• A note on enumerative counting
• Information-theoretic characterizations of recursive infinite strings
• Symmetric alternation captures BPP
• More on BPP and the polynomial-time hierarchy
• Terse, superterse, and verbose sets
• Enumerative counting is hard
• Lowness properties and randomness
• Randomness is Hard
• Reducibility and Completeness for Sets of Integers
• Algebraic methods for interactive proof systems
• IP = PSPACE
• Effective Search Problems
• On the Length of Programs for Computing Finite Binary Sequences
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• Class groups of integral group rings
• A formal theory of inductive inference. Part II