Boolean Operations, Joins, and the Extended Low Hierarchy

Details Boolean Operations, Joins, and the Extended Low Hierarchy Boolean Operations, Joins, and the Extended Low Hierarchy

1999-07-25

arxiv.org/abs/cs/9907037v1

Theoretical Computer Science vol. 205, no. 1-2, pp. 317--327, 1998

Computer Science

Computational Complexity

12 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Boolean Operations, Joins, and the Extended Low Hierarchy does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Boolean Operations, Joins, and the Extended Low Hierarchy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Boolean Operations, Joins, and the Extended Low Hierarchy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-619298