Hausdorff dimension and oracle constructions

DOI10.1016/J.TCS.2006.01.025MaRDI QIDQ2369006zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Relative to a random oracle, NP is not small
• scientific article; zbMATH DE number 4049050
• On relativized probabilistic polynomial time algorithms
• Results on resource-bounded measure
• Hausdorff-dimension and weak truth-table reducibility

Cites work

• scientific article; zbMATH DE number 44693 (Why is no real title available?)
• Algebraic methods for interactive proof systems
• Dimension in Complexity Classes
• Fractal dimension and logarithmic loss unpredictability.
• IP = PSPACE
• On Relativized Polynomial and Exponential Computations
• On collapsing the polynomial-time hierarchy
• 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
• Relativized worlds with an infinite hierarchy
• Scaled dimension and nonuniform complexity
• The random oracle hypothesis is false

Cited in

(3)

• scientific article; zbMATH DE number 4049050 (Why is no real title available?)
• Scaled dimension and the Kolmogorov complexity of Turing-hard sets
• Hausdorff-dimension and weak truth-table reducibility

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

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