A hierarchy for BPP//log based on counting calls to an oracle
From MaRDI portal
Publication:4686644
Recommendations
- On the Power of Threshold Measurements as Oracles
- Axiomatizing physical experiments as oracles to algorithms
- Oracles that measure thresholds: the Turing machine and the broken balance
- Computational complexity with experiments as oracles. II. Upper bounds
- The impact of models of a physical oracle on computational power
Cites work
- scientific article; zbMATH DE number 4066010 (Why is no real title available?)
- scientific article; zbMATH DE number 192916 (Why is no real title available?)
- scientific article; zbMATH DE number 1260390 (Why is no real title available?)
- scientific article; zbMATH DE number 3366923 (Why is no real title available?)
- An analogue-digital Church-Turing thesis
- Classical recursion theory. Vol. II
- Computational complexity with experiments as oracles
- Computational complexity with experiments as oracles. II. Upper bounds
- Computational power of neural networks: a characterization in terms of Kolmogorov complexity
- Computations with oracles that measure vanishing quantities
- Incomputability at the foundations of physics (a study in the philosophy of science)
- Limits to measurement in experiments governed by algorithms
- Oracles and Advice as Measurements
- Oracles that measure thresholds: the Turing machine and the broken balance
- Physical oracles: the Turing machine and the Wheatstone bridge
- Quantum walks: a comprehensive review
- Random orders and gambler's ruin
- The impact of models of a physical oracle on computational power
- Three forms of physical measurement and their computability
- Uncertainty in time
Cited in
(3)
This page was built for publication: A hierarchy for BPP//log\(\star\) based on counting calls to an oracle
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4686644)