Hausdorff dimension and oracle constructions

DOI10.1016/J.TCS.2006.01.025zbMath1088.68068OpenAlexW1983758056MaRDI QIDQ2369006

John M. Hitchcock

Publication date: 28 April 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.01.025

zbMATH Keywords

Hausdorff dimensionComputational complexityOraclesRelativization

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 (1)

Scaled dimension and the Kolmogorov complexity of Turing-hard sets

Cites Work

• Unnamed Item
• The random oracle hypothesis is false
• On collapsing the polynomial-time hierarchy
• Fractal dimension and logarithmic loss unpredictability.
• Relativized worlds with an infinite hierarchy
• Scaled dimension and nonuniform complexity
• On Relativized Polynomial and Exponential Computations
• On relativized exponential and probabilistic complexity classes
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Algebraic methods for interactive proof systems
• IP = PSPACE
• Dimension in Complexity Classes

This page was built for publication: Hausdorff dimension and oracle constructions