A hierarchy for BPP//log based on counting calls to an oracle

DOI10.1007/978-3-319-46376-6_3MaRDI QIDQ4686644zbMATH OpenOpenAlexFDO

Authors Pedro Cortez, José Félix Costa, John V. Tucker, Edwin 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

zbMATH Keywords

random walkpolynomial timeTuring machineoracle queryadvice function

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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)

• The Power of Machines That Control Experiments
• Machines that perform measurements
• A Survey on Analog Models of Computation

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)