A Natural Computation Model of Positive Relativisation
Edwin Beggs, Jose Felix Costa and John V. Tucker
We develop the idea of using a physical experiment as an oracle to an algorithm. Of particular interest are protocols that manage oracle queries and count the resources involved. We investigate the computational power of deterministic and non-deterministic Turing machines connected to two physical oracles, namely, the scatter machine experiment and the smooth scatter machine experiment, which were introduced and studied in some depth earlier. Then we prove relativisation theorems for the conjectures concerning P, NP, PSPACE relative to these two physical oracles. Finally, we reflect generally on physical oracles for complexity theory.
Keywords: Analog-digital computation, scatter machine, polynomial complexity classes, P to PSPACE separation, positive relativisation