Resource Bounded Immunity and Simplicity
<|reference_start|>Resource Bounded Immunity and Simplicity: Revisiting the thirty 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.<|reference_end|>
@article{yamakami2004resource,
    title={Resource Bounded Immunity and Simplicity},
    author={Tomoyuki Yamakami and Toshio Suzuki},
    journal={(journal version) Theoretical Computer Sceince, Vol.347,
  pp.90-129, 2005},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0407015},
    primaryClass={cs.CC cs.DM}
}