Resource Bounded Immunity and Simplicity

Details Resource Bounded Immunity and Simplicity Resource Bounded Immunity and Simplicity

2004-07-06

arxiv.org/abs/cs/0407015v2

(journal version) Theoretical Computer Sceince, Vol.347, pp.90-129, 2005

Computer Science

Computational Complexity

This is a complete version of the conference paper that appeared in the Proceedings of the 3rd IFIP International Conference o

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Resource Bounded Immunity and Simplicity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Resource Bounded Immunity and Simplicity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Resource Bounded Immunity and Simplicity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-139491