Boolean Operations, Joins, and the Extended Low Hierarchy
<|reference_start|>Boolean Operations, Joins, and the Extended Low Hierarchy: 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.<|reference_end|>
@article{hemaspaandra1999boolean,
    title={Boolean Operations, Joins, and the Extended Low Hierarchy},
    author={Lane A. Hemaspaandra, Zhigen Jiang, Joerg Rothe and Osamu Watanabe},
    journal={Theoretical Computer Science vol. 205, no. 1-2, pp. 317--327, 1998},
    year={1999},
    number={earlier version appeared as University of Rochester TR-96-627},
    archivePrefix={arXiv},
    eprint={cs/9907037},
    primaryClass={cs.CC}
}