A recent result in the study of relativized complexity classes says that relative to some recursive oracle set A there are sets L in (NP(A) which contain no infinite subset belonging to P(A). (Here NP(A) and P(A) denote the relativized versions of NP, resp. P.) Such sets L are are called P(A)-immune and roughly speaking this means that except in a trivial way by finite sets, L cannot be approximated by sets in the corresponding deterministic complexity class P(A).

In order to investigate the reasons for such behavior more closely, the authors consider refinements of the step from P(A) to NPA), which are obtained by bounding the amount of nondeterminism; i.e., the number of nondeterministic computation steps. In this way, it is possible to build infinite hierarchies such that the immunity property still holds for every step in these hierarchies. Moreover, other generalizations are obtained by bounding the number times the oracle may be consulted during a computation. All results are based on refinements of Schönning’s proof of the original result where both bounds on nondeterminism and oracle queries are given by the time bound. This proof is extracted and presented in a concise way before generalization is done. As pointed out in the discussion, this paper in particular exhibits the power of nondeterminism when used in oracle machines.