Abstract
As part of a study of almost-everywhere complex sets, we investigate sets that are immune to AC0; that is, sets with no infinite subset in AC0. We show that such sets exist in PPP and in DSPACE(log n log n). Our main result is an oracle construction indicating that any improvement in these immunity results will represent a significant advance, in that we show that any answer to the question: Are there sets in NP that are immune to AC0? will provide non-relativizable proof techniques suitable for attacking the Ntime vs Dtime question. That is, we show that the existence or nonexistence of AC0-immune sets in NP has consequences concerning the complexity of sets indeterministic and nondeterministic exponential time.