Immunity, relativizations, and nondeterminism. (English) Zbl 0558.68039

In the recursivity theory, a set of natural numbers is said to be immune if it is infinite and does not contain any infinite r.e. subset. An analogous notion of immunity with respect to complexity classes has been proposed by Flajolet and Steyaert: given a complexity class \({\mathbb{C}}\), a set L is \({\mathbb{C}}\)-immune if L is infinite and no infinite subset of L is in \({\mathbb{C}}\). In studying the existence of immune sets with respect to particular complexity classes, a first result has been given by Bennett and Gill: there exists a set A such that NP(A) has a P(A) immune set. Here, NP(A) and P(A) are the nondeterministic polynomial and deterministic polynomial relativized complexity classes.
In this very technical paper, this result is generalized by giving conditions on a set \({\mathbb{F}}\) of running times such that there exist a set \({\mathcal A}\) and a set \({\mathcal L}\) in NTIME(\({\mathbb{F}},{\mathcal A})\) that is immune with respect to the class of languages accepted relative to \({\mathcal A}\) by any class of oracle machines such that the set of strings queried in all computations is bounded in size by a function in \({\mathbb{F}}\). The Second Immunity Theorem stated in the paper extends a result of Xu, Doner and Book showing that one can find a set \({\mathcal A}\) such that there is an infinite hierarchy of classes relative to \({\mathcal A}\) where each class is obtained by increasing the amount of nondeterminism allowed for the preceding one. Here it is shown the existence, for every class of these hierarchies, of a set which has no infinite subsets in the preceding class, i.e. is immune in it.
Reviewer: G.Mauri


68Q25 Analysis of algorithms and problem complexity
Full Text: DOI