2 documents found, page 1 of 1
Classifying the computational power of stochastic physical oracles
Beggs, Edwin; Cortez, Pedro; Costa, José Félix; Tucker, John V.Consider a computability and complexity theory in which the classical set-theoretic oracle to a Turing machine is replaced by a physical process, and oracle queries return measurements of physical behaviour. The idea of such physical oracles is relevant to many disparate situations, but research has focussed on physical oracles that were classic deterministic experiments which measure physical quantities. In th...
A hierarchy for BPP//log* based on counting calls to an oracle
Beggs, Edwin; Cortez, Pedro; Costa, José Félix; Tucker, John V.Algorithms whose computations involve making physical measurements can be modelled by Turing machines with oracles that are physical systems and oracle queries that obtain data from observation and measurement. The computational power of many of these physical oracles has been established using non-uniform complexity classes; in particular, for large classes of deterministic physical oracles, with fixed error m...