Robust algorithms: A different approach to oracles

AbstractA new notion of an oracle machine being ‘helped’ by an oracle set is introduced. It is required that the oracle machine is ‘robust’, i.e., it always computes the same set independent of the oracle. The main result states that the class of sets that can be computed by deterministic polynomial time algorithms being helped by some oracle set is exactly NP ∩ co-NP. Some connections to probabilistic classes are also investigated