Closure and nonclosure properties of the classes of compressible and rankable sets

摘要

The rankable and the compressible sets have been studied for more than a quarter of a century. We ask whether these classes are closed under the most important boolean and other operations. We study this question for both polynomial-time and recursion-theoretic compression and ranking, and for almost every case arrive at a Closed, a Not-Closed, or a Closed-Iff-Well-Known-Complexity-Classes-Collapse result. Although compression and ranking classes are capturing something quite natural about the structure of sets, it turns out that these classes are quite fragile with respect to closure properties, and many fail to possess even the most basic of closure properties. For example, we show that with respect to the join (aka disjoint union) operation: the P-rankable sets are not closed, whether the semistrongly P-rankable sets are closed is closely linked to whether , and the strongly P-rankable sets are closed.