From Logarithmic Advice to Single-Bit Advice

DOI10.1007/978-3-642-22670-0_13zbMath1343.68080OpenAlexW2173156022MaRDI QIDQ3088181

Oded Goldreich, Luca Trevisan

Publication date: 19 August 2011

Published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22670-0_13

zbMATH Keywords

machines that take adviceseparations among complexity classes

Mathematics Subject Classification ID

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

Related Items (1)

Time hierarchies for cryptographic function inversion with advice

Cites Work

• Unnamed Item
• A generic time hierarchy with one bit of advice

This page was built for publication: From Logarithmic Advice to Single-Bit Advice