Robust algorithms: A different approach to oracles

A 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.

Authors

• Uwe Schöning

Keywords

No keywords are indexed for this paper.