Scaled dimension and the Kolmogorov complexity of Turing-hard sets
type: Item
instance of: scholarly article
title: Scaled dimension and the Kolmogorov complexity of Turing-hard sets
zbMATH Open document ID: 1166.68020
author: John M. Hitchcock
author: María López-Valdés
author: Elvira Mayordomo
published in: Theory of Computing Systems
publication date: 2009-05-08T00:00:00Z
Mathematics Subject Classification ID: 68Q30
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 5552163
zbMATH Keywords: effective dimension
zbMATH Keywords: scaled dimension
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: Turing-hard sets
Wikidata QID: Q60578972
MaRDI profile type: Publication
full work available at URL: s00224-007-9013-x
OpenAlex ID: W2044316629
cites work: Genericity and measure for exponential time
cites work: Effective Strong Dimension in Algorithmic Information and Computational Complexity
cites work: Hard sets are hard to find
cites work: On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line
cites work: A Theory of Program Size Formally Identical to Information Theory
cites work: A note on dimensions of polynomial size circuits
cites work: Fractal dimension and logarithmic loss unpredictability.
cites work: Gales suffice for constructive dimension
cites work: Small Spans in Scaled Dimension
cites work: Hausdorff dimension and oracle constructions
cites work: Base invariance of feasible dimension
cites work: FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
cites work: Dimension, entropy rates, and compression
cites work: Scaled dimension and nonuniform complexity
cites work: Partial bi-immunity, scaled dimension, and NP-completeness
cites work: The Complexity and Distribution of Hard Problems
cites work: Completeness and weak completeness under polynomial-size circuits
cites work: Q4070738
cites work: Q4337021
cites work: Mathematical Foundations of Computer Science 2005
cites work: Dimension in Complexity Classes
cites work: The dimensions of individual strings and sequences
cites work: A Kolmogorov complexity characterization of constructive Hausdorff dimension.
cites work: Q3705346
cites work: Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
cites work: Kolmogorov complexity and Hausdorff dimension
cites work: A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
cites work: THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
DOI: 10.1007/S00224-007-9013-X
description: scientific article; zbMATH DE number 5552163