Abstract
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.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.