×

P-selectivity, immunity, and the power of one bit. (English) Zbl 1175.03024

Wiedermann, Jiří (ed.) et al., SOFSEM 2006: Theory and practice of computer science. 32nd conference on current trends in theory and practice of computer science, Měřín, Czech Republic, January 21–27, 2006. Proceedings. Berlin: Springer (ISBN 3-540-31198-X/pbk). Lecture Notes in Computer Science 3831, 323-331 (2006).
Summary: 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^p_2/1\)-immune.
For the entire collection see [Zbl 1097.68010].

MSC:

03D15 Complexity of computation (including implicit computational complexity)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI