A Hierarchy for $$ BPP //\log \!\star $$ B P P / / log ⋆ Based on Counting Calls to an Oracle
From MaRDI portal
Publication:4686644
DOI10.1007/978-3-319-46376-6_3zbMath1396.68049OpenAlexW2547032772MaRDI QIDQ4686644
Pedro Cortez, Costa, José Félix, J. V. Tucker, Edwin J. Beggs
Publication date: 4 October 2018
Published in: Emergent Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-46376-6_3
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (3)
Machines that perform measurements ⋮ The Power of Machines That Control Experiments ⋮ A Survey on Analog Models of Computation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Physical oracles: the Turing machine and the Wheatstone bridge
- Classical recursion theory. Vol. II
- Quantum walks: a comprehensive review
- Random orders and gambler's ruin
- The impact of models of a physical oracle on computational power
- AN ANALOGUE-DIGITAL CHURCH-TURING THESIS
- Limits to measurement in experiments governed by algorithms
- Oracles and Advice as Measurements
- 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
- Uncertainty in Time
- THREE FORMS OF PHYSICAL MEASUREMENT AND THEIR COMPUTABILITY
- Oracles that measure thresholds: the Turing machine and the broken balance
- Incomputability at the foundations of physics (A study in the philosophy of science)
- Computational complexity with experiments as oracles
This page was built for publication: A Hierarchy for $$ BPP //\log \!\star $$ B P P / / log ⋆ Based on Counting Calls to an Oracle
