From logarithmic advice to single-bit advice

DOI10.1007/978-3-642-22670-0_13MaRDI QIDQ3088181zbMATH OpenOpenAlexFDO

Authors Oded Goldreich, Luca Trevisan, Madhu Sudan

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)

Recommendations

• A generic time hierarchy with one bit of advice
• THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA
• scientific article; zbMATH DE number 1962843
• The roles of advice to one-tape linear-time Turing machines and finite automata (extended abstract)
• Space hierarchy results for randomized models

Cites work

• A generic time hierarchy with one bit of advice
• scientific article; zbMATH DE number 2019635 (Why is no real title available?)

Cited in

(3)

• A generic time hierarchy with one bit of advice
• scientific article; zbMATH DE number 1962843 (Why is no real title available?)
• Time hierarchies for cryptographic function inversion with advice

This page was built for publication: From logarithmic advice to single-bit advice

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