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

DOI10.1007/978-3-319-46376-6_3zbMATH Open1396.68049OpenAlexW2547032772MaRDI QIDQ4686644FDOQ4686644

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

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

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)

Cites Work

• Title not available (Why is that?)
• Quantum walks: a comprehensive review
• Title not available (Why is that?)
• Classical recursion theory. Vol. II
• Title not available (Why is that?)
• The impact of models of a physical oracle on computational power
• Limits to measurement in experiments governed by algorithms
• Physical oracles: the Turing machine and the Wheatstone bridge
• Computational power of neural networks: a characterization in terms of Kolmogorov complexity
• Title not available (Why is that?)
• Computational complexity with experiments as oracles
• Oracles and Advice as Measurements
• Computational complexity with experiments as oracles. II. Upper bounds
• An analogue-digital Church-Turing thesis
• THREE FORMS OF PHYSICAL MEASUREMENT AND THEIR COMPUTABILITY
• Random orders and gambler's ruin
• Incomputability at the foundations of physics (A study in the philosophy of science)
• Oracles that measure thresholds: the Turing machine and the broken balance
• Uncertainty in Time
• Computations with oracles that measure vanishing quantities

Cited In (3)

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

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)