A carregar...
Publicação
Classifying the computational power of stochastic physical oracles
Orientador(es)
Resumo(s)
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 this paper, we broaden the scope
of the theory of physical oracles by tackling non-deterministic
systems. We examine examples of three types of non-determinism,
namely systems that are: (1) physically nondeterministic,
as in quantum phenomena; (2) physically deterministic but
whose physical theory is non-deterministic, as in statistical mechanics;
and (3) physically deterministic but whose computational
theory is non-deterministic caused by error margins. Physical
oracles that have probabilistic theories we call stochastic
physical oracles. We propose a set SPO of axioms for a basic
form of stochastic oracles. We prove that Turing machines
equipped with a physical oracle satisfying the axioms SPO compute
precisely the non-uniform complexity class BPP//log* in
polynomial time. This result of BPP/log* is a computational
limit to a great range of classical and non-classical measurement,
and of analogue-digital computation in polynomial time under
general conditions.