P-Selectivity, Immunity, and the Power of One Bit
| dc.creator | Hemaspaandra, Lane A. | |
| dc.creator | Torenvliet, Leen | |
| dc.date | 2005-04-25 | |
| dc.date | 2005-12-07 | |
| dc.date.accessioned | 2026-07-07T06:38:08Z | |
| dc.date.available | 2026-07-07T06:38:08Z | |
| dc.description | 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 Π_2^p/1-immune. | |
| dc.identifier | https://arxiv.org/abs/cs/0504096 | |
| dc.identifier | http://arxiv.org/abs/cs/0504096 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/100633 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.1.3 | |
| dc.title | P-Selectivity, Immunity, and the Power of One Bit | |
| dc.type | text |