Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-066 | 6th July 2004 00:00

Resource Bounded Immunity and Simplicity

RSS-Feed




TR04-066
Authors: Tomoyuki Yamakami, Toshio Suzuki
Publication: 9th August 2004 20:17
Downloads: 3106
Keywords: 


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.



ISSN 1433-8092 | Imprint