Scaled dimension and the Kolmogorov complexity of Turing-hard sets

DOI10.1007/s00224-007-9013-xzbMath1166.68020OpenAlexW2044316629WikidataQ60578972 ScholiaQ60578972MaRDI QIDQ1015370

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

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

Kolmogorov complexityeffective dimensionscaled dimensionTuring-hard sets

Mathematics Subject Classification ID

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

Related Items (1)

Exact constructive and computable dimensions

Cites Work

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

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