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

Abstract

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 margins constraining the exchange of data between algorithm and oracle, the computational power has been shown to be the non-uniform class BPP//log⋆ . In this paper, we consider non-deterministic oracles that can be modelled by random walks on the line. We show how to classify computations within BPP//log⋆ by making an infinite non-collapsing hierarchy between BPP//log⋆ and BPP . The hierarchy rests on the theorem that the number of calls to the physical oracle correlates with the size of the responses to queries.