P-Selectivity, Immunity, and the Power of One Bit

Details P-Selectivity, Immunity, and the Power of One Bit P-Selectivity, Immunity, and the Power of One Bit

2005-04-25

arxiv.org/abs/cs/0504096v2

Computer Science

Computational Complexity

Scientific paper

We prove that P-sel, the class of all P-selective sets, is EXP-immune, but is not EXP/1-immune. That is, we prove that some infinite P-selective set has no infinite EXP-time subset, but we also prove that every infinite P-selective set has some infinite subset in EXP/1. Informally put, the immunity of P-sel is so fragile that it is pierced by a single bit of information. The above claims follow from broader results that we obtain about the immunity of the P-selective sets. In particular, we prove that for every recursive function f, P-sel is DTIME(f)-immune. Yet we also prove that P-sel is not \Pi_2^p/1-immune.

Affiliated with

Also associated with

No associations

Rating

P-Selectivity, Immunity, and the Power of One Bit 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 P-Selectivity, Immunity, and the Power of One Bit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and P-Selectivity, Immunity, and the Power of One Bit will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-468272