A generic time hierarchy with one bit of advice

DOI10.1007/S00037-007-0227-8MaRDI QIDQ2472432zbMATH OpenOpenAlexFDO

Authors Dieter Van Melkebeek, Konstantin Pervyshev

Publication date 22 February 2008

Published in Computational Complexity (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://doi.org/10.1007/s00037-007-0227-8

zbMATH Keywords

delayed diagonalizationnon-uniform modelsprobabilistic complexity classessemantic modelstime hierarchy

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum computation (81P68)

Recommendations

• Space hierarchy results for randomized and other semantic models
• Space hierarchy results for randomized models
• From logarithmic advice to single-bit advice
• THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA
• New non-uniform lower bounds for uniform classes

Cited in

(13)

• On average time hierarchies
• Catalytic space: non-determinism and hierarchy
• Random access to advice strings and collapsing results
• From logarithmic advice to single-bit advice
• Structural Complexity of AvgBPP
• Space hierarchy results for randomized models
• scientific article; zbMATH DE number 7250147 (Why is no real title available?)
• Algorithms and Computation
• The power of natural properties as oracles
• Space hierarchy results for randomized and other semantic models
• Structural complexity of AvgBPP
• Oblivious complexity classes revisited: lower bounds and hierarchies
• Time hierarchies for cryptographic function inversion with advice

This page was built for publication: A generic time hierarchy with one bit of advice

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