Resource bounded immunity and simplicity
Revisiting the 30-years-old notions of resource-bounded immunity and simplicity, we investigate the structural characteristics of various immunity notions: strong immunity, almost immunity, and hyperimmunity as well as their corresponding simplicity notions. We also study limited immunity and simplicity, called k-immunity and feasible k-immunity, and their simplicity notions. Finally, we propose the k-immune hypothesis as a working hypothesis that guarantees the existence of simple sets in NP (c) 2005 Elsevier B.V. All rights reserved.
simple set immune set complete set weak forcing generic oracle random oracle