P-Selectivity, Immunity, and the Power of One Bit
<|reference_start|>P-Selectivity, Immunity, and the Power of One Bit: 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.<|reference_end|>
@article{hemaspaandra2005p-selectivity,,
    title={P-Selectivity, Immunity, and the Power of One Bit},
    author={Lane A. Hemaspaandra and Leen Torenvliet},
    journal={arXiv preprint arXiv:cs/0504096},
    year={2005},
    number={URCS-TR-2005-864},
    archivePrefix={arXiv},
    eprint={cs/0504096},
    primaryClass={cs.CC}
}