Enumerations of the Kolmogorov function

DOI10.2178/JSL/1146620156MaRDI QIDQ5480623zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Enumerations including laconic enumerators
• On Languages with Very High Space-Bounded Kolmogorov Complexity
• Power from Random Strings
• scientific article; zbMATH DE number 107775
• What can be efficiently reduced to the Kolmogorov-random strings?

Cites work

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

Cited in

(12)

• Short lists with short programs in short time
• Searching for shortest and least programs
• Kolmogorov complexity of enumerating finite sets
• Enumerations including laconic enumerators
• The axiomatic power of Kolmogorov complexity
• Extracting randomness within a subset is hard
• On approximate decidability of minimal programs
• Short lists for shortest descriptions in short time
• Cone avoiding closed sets
• Kolmogorov entropy in the context of computability theory
• Index sets and universal numberings
• Kolmogorov complexity and degrees of tally sets

This page was built for publication: Enumerations of the Kolmogorov function

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