Infinitely‐Often Autoreducible Sets

DOI10.1137/S0097539704441630MaRDI QIDQ3446809zbMATH OpenOpenAlexFDO

Authors Richard Beigel, Lance Fortnow, Frank Stephan

Publication date 26 June 2007

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539704441630

zbMATH Keywords

computational complexityalgorithmic randomnessHausdorff-dimensionautoreducible setsexponential-time computable setsinfinitely-often autoreducible sets

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• Algorithms and Computation
• Probabilistic autoreductions
• Separating Complexity Classes Using Autoreducibility
• scientific article; zbMATH DE number 1497861
• scientific article; zbMATH DE number 1929940

Cited in

(3)

• On being incoherent without being very hard
• scientific article; zbMATH DE number 1759420 (Why is no real title available?)
• Algorithms and Computation

This page was built for publication: Infinitely‐Often Autoreducible Sets

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