Scaled dimension and nonuniform complexity

DOI10.1016/J.JCSS.2003.09.001MaRDI QIDQ1880776zbMATH OpenOpenAlexWikidataFDO

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

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

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

Recommendations

• scientific article; zbMATH DE number 2038717
• Dimension in Complexity Classes
• scientific article; zbMATH DE number 1346358
• Mathematical Foundations of Computer Science 2004
• Scaled dimension and the Kolmogorov complexity of Turing-hard sets

Cites work

• scientific article; zbMATH DE number 2089375 (Why is no real title available?)
• scientific article; zbMATH DE number 3133387 (Why is no real title available?)
• scientific article; zbMATH DE number 44693 (Why is no real title available?)
• scientific article; zbMATH DE number 1335897 (Why is no real title available?)
• scientific article; zbMATH DE number 3324894 (Why is no real title available?)
• A unified approach to the definition of random sequences
• Algorithms and Computation
• Almost everywhere high nonuniform complexity
• Completeness and weak completeness under polynomial-size circuits
• Dimension in Complexity Classes
• Fractal dimension and logarithmic loss unpredictability.
• Klassifikation der Zufallsgesetze nach Komplexit�t und Ordnung
• MAX3SAT is exponentially hard to approximate if NP has positive dimension.
• Process complexity and effective random tests
• STACS 2004
• THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES
• The dimensions of individual strings and sequences
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)

Cited in

(16)

• scientific article; zbMATH DE number 2038717 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2004
• Subcomputable Hausdorff function dimension
• A note on dimensions of polynomial size circuits
• Resource-bounded strong dimension versus resource-bounded category
• Pushdown dimension
• Extending the reach of the point-to-set principle
• A characterization of constructive dimension
• Scaled dimension and the Kolmogorov complexity of Turing-hard sets
• Partial bi-immunity, scaled dimension, and NP-completeness
• Intrinsic Complexity and Scaling Laws: From Random Fields to Random Vectors
• Dimension- and time-hierarchies for small time bounds.
• Hausdorff dimension and oracle constructions
• Dimension, entropy rates, and compression
• Exact constructive and computable dimensions
• Dimension in Complexity Classes

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

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