2005/04/25 by Lane A. Hemaspaandra, Hemaspaandra, Lane A., Leen Torenvliet +1
Computer Science · Mathematics · #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.cs/0504096
openalex publication_date 2005/04/25 · arxiv created 2005/12/07 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Π2p/1-immune.