Simplicity, Relativizations and Nondeterminism
José L. Balcázar · SIAM Journal on Computing · 1985
Relativizations of complexity classes in which simple sets exist are considered. A recursive oracle is constructed relative to which a simple set exists for NP. Some other general theorems are proven, showing that the time bounds are not a crucial hypothesis; bounds on the way in which the oracle is accessible, namely, the number of queries and/or the number of nondeterministic steps, are shown to be the fundamental hypothesis. As a result, simple sets are shown to exist in many different relativized complexity classes.