Logarithmic advice classes
From MaRDI portal
Publication:1193903
DOI10.1016/0304-3975(92)90353-HzbMath0761.68040MaRDI QIDQ1193903
Uwe Schoening, José L. Balcázar
Publication date: 27 September 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
A Note on polynomial-size circuits with low resource-bounded Kolmogorov complexity, Complexity classes between $\Theta _k^P$ and $\Delta _k^P$, Degrees and reducibilities of easy tally sets, Proof systems that take advice, Average-case intractability vs. worst-case intractability, Modulo classes and logarithmic advice, On sets Turing reducible to p-selective sets, The structure of logarithmic advice complexity classes, Competing provers yield improved Karp-Lipton collapse results, Machines that perform measurements, Does Advice Help to Prove Propositional Tautologies?
Cites Work
- Unnamed Item
- Unnamed Item
- Some consequences of non-uniform conditions on uniform classes
- On small generators
- A low and a high hierarchy within NP
- On self-reducibility and weak P-selectivity
- Strong nondeterministic polynomial-time reducibilities
- On helping by robust oracle machines
- On characterizations of the class PSPACE/poly
- On sparse sets in NP-P
- The polynomial-time hierarchy
- Computation times of NP sets of different densities
- Complexity of Presburger arithmetic with fixed quantifier dimension
- The polynomial-time hierarchy and sparse oracles
- On Circuit-Size Complexity and the Low Hierarchy in NP
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Computational Complexity of Probabilistic Turing Machines
- Polynomial Time Enumeration Reducibility
- Tally languages and complexity classes
