Resource-bounded strong dimension versus resource-bounded category

DOI10.1016/j.ipl.2005.05.001zbMath1185.68359OpenAlexW2088134116MaRDI QIDQ1041791

John M. Hitchcock, A. Pavan

Publication date: 4 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.05.001

zbMATH Keywords

computational complexityresource-bounded measureresource-bounded categoryresource-bounded dimension

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Extracting Kolmogorov complexity with applications to dimension zero-one laws ⋮ Algorithmic Fractal Dimensions in Geometric Measure Theory

Cites Work

• Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups
• Almost everywhere high nonuniform complexity
• Almost every set in exponential time is P-bi-immune
• Genericity and measure for exponential time
• Category and Measure in Complexity Classes
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• Two definitions of fractional dimension
• Dimension in Complexity Classes
• Unnamed Item
• Unnamed Item

This page was built for publication: Resource-bounded strong dimension versus resource-bounded category