Scaled dimension and nonuniform complexity

DOI10.1016/j.jcss.2003.09.001zbMath1084.68055OpenAlexW1997925883WikidataQ60578982 ScholiaQ60578982MaRDI QIDQ1880776

John M. Hitchcock, Elvira Mayordomo, Jack H. Lutz

Publication date: 1 October 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2003.09.001

zbMATH Keywords

Hausdorff dimensionKolmogorov complexityComputational complexityCircuit complexityResource-bounded dimensionGalesScaled dimension

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Hausdorff and packing measures (28A78)

Related Items (10)

Hausdorff dimension and oracle constructions ⋮ Extending the reach of the point-to-set principle ⋮ Exact constructive and computable dimensions ⋮ Subcomputable Hausdorff function dimension ⋮ Partial bi-immunity, scaled dimension, and NP-completeness ⋮ Dimension, entropy rates, and compression ⋮ A note on dimensions of polynomial size circuits ⋮ Pushdown dimension ⋮ A characterization of constructive dimension ⋮ Scaled dimension and the Kolmogorov complexity of Turing-hard sets

Cites Work

• Almost everywhere high nonuniform complexity
• Fractal dimension and logarithmic loss unpredictability.
• MAX3SAT is exponentially hard to approximate if NP has positive dimension.
• The dimensions of individual strings and sequences
• Completeness and weak completeness under polynomial-size circuits
• Process complexity and effective random tests
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• Dimension in Complexity Classes
• Algorithms and Computation
• STACS 2004
• [https://portal.mardi4nfdi.de/wiki/Publication:5587565 Klassifikation der Zufallsgesetze nach Komplexit�t und Ordnung]
• A unified approach to the definition of random sequences
• THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Scaled dimension and nonuniform complexity