Boolean operations, joins, and the extended low hierarchy

Article, Preprint English OPEN
Hemaspaandra, Lane A.; Jiang, Zhigen; Rothe, Joerg; Watanabe, Osamu;

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 te... View more
Share - Bookmark