The structure of logarithmic advice complexity classes
From MaRDI portal
Publication:1275000
DOI10.1016/S0304-3975(98)00066-8zbMath0912.68045MaRDI QIDQ1275000
José L. Balcázar, Montserrat Hermo
Publication date: 12 January 1999
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (9)
Polynomial time quantum computation with advice ⋮ General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results ⋮ Axiomatizing physical experiments as oracles to algorithms ⋮ Machines that perform measurements ⋮ Degrees and reducibilities of easy tally sets ⋮ On the Complexity of Measurement in Classical Physics ⋮ THREE FORMS OF PHYSICAL MEASUREMENT AND THEIR COMPUTABILITY ⋮ Limits to measurement in experiments governed by algorithms ⋮ Computational complexity with experiments as oracles
Cites Work
- Unnamed Item
- Unnamed Item
- Kolmogorov complexity and degrees of tally sets
- On the notion of infinite pseudorandom sequences
- On helping by robust oracle machines
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- Logarithmic advice classes
- Analog computation via neural networks
- Reducibilities on tally and sparse sets
- Bounded Query Classes
- Sparse Sets, Lowness and Highness
- The difference and truth-table hierarchies for NP
- On Sets Truth-Table Reducible to Sparse Sets
- Relating Equivalence and Reducibility to Sparse Sets
- Instance complexity
- Lower bounds for the low hierarchy
- Computational power of neural networks: a characterization in terms of Kolmogorov complexity
- Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
- A refinement of the low and high hierarchies
- Upper bounds for the complexity of sparse and tally descriptions
- Degrees and reducibilities of easy tally sets
This page was built for publication: The structure of logarithmic advice complexity classes
