Boolean Operations, Joins, and the Extended Low Hierarchy
| dc.creator | Hemaspaandra, Lane A. | |
| dc.creator | Jiang, Zhigen | |
| dc.creator | Rothe, Joerg | |
| dc.creator | Watanabe, Osamu | |
| dc.date | 1999-07-25 | |
| dc.date.accessioned | 2026-07-07T03:24:16Z | |
| dc.date.available | 2026-07-07T03:24:16Z | |
| dc.description | We prove that the join of two sets may actually fall into a lower level of the extended low hierarchy than either of the sets. In particular, there exist sets that are not in the second level of the extended low hierarchy, EL_2, yet their join is in EL_2. That is, in terms of extended lowness, the join operator can lower complexity. Since in a strong intuitive sense the join does not lower complexity, our result suggests that the extended low hierarchy is unnatural as a complexity measure. We also study the closure properties of EL_ and prove that EL_2 is not closed under certain Boolean operations. To this end, we establish the first known (and optimal) EL_2 lower bounds for certain notions generalizing Selman's P-selectivity, which may be regarded as an interesting result in its own right. | |
| dc.description | 12 pages | |
| dc.identifier | https://arxiv.org/abs/cs/9907037 | |
| dc.identifier | http://arxiv.org/abs/cs/9907037 | |
| dc.identifier | Theoretical Computer Science vol. 205, no. 1-2, pp. 317--327, 1998 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/33259 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.1.3 | |
| dc.title | Boolean Operations, Joins, and the Extended Low Hierarchy | |
| dc.type | text |