Closure and Nonclosure Properties of the Compressible and Rankable Sets

摘要

The rankable and compressible sets have been studied for more than a quarter of a century, ever since Allender [2] and Goldberg and Sipser [7] introduced the formal study of polynomial-time ranking. Yet even after all that time, whether the rankable and compressible sets are closed under the most important boolean and other operations remains essentially unexplored. The present paper studies these questions for both polynomial-time and recursion-theoretic compression and ranking, and for almost every case arrives at a Closed, a Not-Closed, or a Closed-Iff-Well-Known-Complexity-Classes-Collapse result for the given operation. Even though compression and ranking classes are capturing something quite natural about the structure of sets, it turns out that they 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 P = UP ∩ coUP, and the strongly P-rankable sets are closed.