The structure of logarithmic advice complexity classes
From MaRDI portal
Recommendations
- Bounding the complexity of advice functions
- Advice classes of parametrized tractability
- A note on the advice complexity of multipass randomized logspace
- Applicative theories for logarithmic complexity classes
- On the Structure of Logspace Probabilistic Complexity Classes
- On the structure of log-space probabilistic complexity classes (extended abstract)
- The relative power of logspace and polynomial time reductions
- Advice complexity and barely random algorithms
- Advice complexity and barely random algorithms
- On generic complexity of the discrete logarithm problem
Cites work
- A refinement of the low and high hierarchies
- Analog computation via neural networks
- Bounded Query Classes
- Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
- Computational power of neural networks: a characterization in terms of Kolmogorov complexity
- Degrees and reducibilities of easy tally sets
- scientific article; zbMATH DE number 3917710 (Why is no real title available?)
- scientific article; zbMATH DE number 512798 (Why is no real title available?)
- Instance complexity
- Kolmogorov complexity and degrees of tally sets
- Logarithmic advice classes
- Lower bounds for the low hierarchy
- On helping by robust oracle machines
- On Sets Truth-Table Reducible to Sparse Sets
- On the notion of infinite pseudorandom sequences
- Reducibilities on tally and sparse sets
- Relating Equivalence and Reducibility to Sparse Sets
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- Sparse Sets, Lowness and Highness
- The difference and truth-table hierarchies for NP
- Upper bounds for the complexity of sparse and tally descriptions
Cited in
(16)- Logarithmic advice classes
- Applicative theories for logarithmic complexity classes
- Polynomial time quantum computation with advice
- Machines that perform measurements
- Axiomatizing physical experiments as oracles to algorithms
- Limits to measurement in experiments governed by algorithms
- On the Complexity of Measurement in Classical Physics
- scientific article; zbMATH DE number 3990861 (Why is no real title available?)
- A Note on polynomial-size circuits with low resource-bounded Kolmogorov complexity
- General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results
- On the Structure of Logspace Probabilistic Complexity Classes
- Degrees and reducibilities of easy tally sets
- Three forms of physical measurement and their computability
- Computational complexity with experiments as oracles
- Modulo classes and logarithmic advice
- Advice classes of parametrized tractability
This page was built for publication: The structure of logarithmic advice complexity classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1275000)
