Robust Oracle Machines revisited
V. Arvind · 2015
We revisit robust machines and helping oracles introduced by Uwe Schöning [23] three decades ago. A robust oracle machine always accepts the same language, regardless of the oracle. An oracle A is said to help a robust machine if oracle access to A “speeds up ” the machine and makes it polynomial-time bounded. Ro-bust machines with helping oracles actually models interactive computation, and can be seen as a precursor to interactive proofs. We discuss these connections and point out how robust oracle machines relate to some recently defined classes like oblivious NP and oblivious MA [15]. As we keep pace with new developments in the field, it is also worthwhile re-calling some of the older ideas and results. Robust machines and helping oracles are a nice example.