A Natural Computation Model of Positive Relativisation

作者：Beggs Edwin; Costa Jose Felix^*; Tucker John V

来源：International Journal of Unconventional Computing, 2014, 10(1-2): 111-141.

• Analog-digital computation
• scatter machine
• polynomial complexity classes
• P to PSPACE separation
• positive relativisation

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.

• 出版日期2014