Simplicity, relativizations and nondeterminism. (English) Zbl 0567.68027

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.


68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)
Full Text: DOI Link