2 papers
cs.CC1999
Boolean Operations, Joins, and the Extended Low Hierarchy
Lane A. Hemaspaandra, Zhigen Jiang, Joerg Rothe +1
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 s…
cs.CC1999
Polynomial-Time Multi-Selectivity
Lane A. Hemaspaandra, Zhigen Jiang, Joerg Rothe +1
We introduce a generalization of Selman's P-selectivity that yields a more flexible notion of selectivity, called (polynomial-time) multi-selectivity, in which the selector is allo…