Hausdorff dimension and oracle constructions

DOI10.1016/J.TCS.2006.01.025zbMATH Open1088.68068OpenAlexW1983758056MaRDI QIDQ2369006FDOQ2369006

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

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

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)

Cites Work

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

Cited In (3)

• Title not available (Why is that?)
• 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)