Scaled dimension and the Kolmogorov complexity of Turing-hard sets

DOI10.1007/S00224-007-9013-XMaRDI QIDQ1015370zbMATH OpenOpenAlexWikidataFDO

Authors John M. Hitchcock, María López-Valdés, Elvira Mayordomo

Publication date 8 May 2009

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

Full work available at URL https://doi.org/10.1007/s00224-007-9013-x

zbMATH Keywords

effective dimensionKolmogorov complexityscaled dimensionTuring-hard sets

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Mathematical Foundations of Computer Science 2004
• Small Spans in Scaled Dimension
• scientific article; zbMATH DE number 2038717
• Scaled dimension and nonuniform complexity
• Constructive dimension equals Kolmogorov complexity

Cites work

• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• A note on dimensions of polynomial size circuits
• A Theory of Program Size Formally Identical to Information Theory
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• Base invariance of feasible dimension
• Completeness and weak completeness under polynomial-size circuits
• Dimension in Complexity Classes
• Dimension, entropy rates, and compression
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• Fractal dimension and logarithmic loss unpredictability.
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Gales suffice for constructive dimension
• Genericity and measure for exponential time
• Hard sets are hard to find
• Hausdorff dimension and oracle constructions
• scientific article; zbMATH DE number 3930883 (Why is no real title available?)
• scientific article; zbMATH DE number 3489016 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• Kolmogorov complexity and Hausdorff dimension
• Mathematical Foundations of Computer Science 2005
• Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
• On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line
• Partial bi-immunity, scaled dimension, and NP-completeness
• Scaled dimension and nonuniform complexity
• Small Spans in Scaled Dimension
• The Complexity and Distribution of Hard Problems
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The dimensions of individual strings and sequences

Cited in

(4)

• Exact constructive and computable dimensions
• Scaled dimension and nonuniform complexity
• scientific article; zbMATH DE number 2038717 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2004

This page was built for publication: Scaled dimension and the Kolmogorov complexity of Turing-hard sets

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