Closure and nonclosure properties of the compressible and rankable sets

DOI10.1007/978-3-030-13435-8_13MaRDI QIDQ2278274zbMATH OpenOpenAlexFDO

Authors Jackson Abascal, Shir Maimon, Daniel Rubery, Lane A. Hemaspaandra

Publication date 4 December 2019

Full work available at URL https://arxiv.org/abs/1611.01696

zbMATH Keywords

closure propertiescomplexity theorycompressioncomputabilityranking

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Abstract: The rankable and compressible sets have been studied for more than a quarter of a century, ever since Allender [1] and Goldberg and Sipser [6] 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 $cap$ coUP, and the strongly P-rankable sets are closed.

Recommendations

• Closure and nonclosure properties of the classes of compressible and rankable sets
• Finite rank functions of closure spaces on partially ordered set
• Closures of discrete sets in compact spaces
• Closure spaces and completions of posets
• scientific article; zbMATH DE number 2190143
• scientific article; zbMATH DE number 3872246
• scientific article; zbMATH DE number 1160319
• The \(R\)-completion of closure spaces
• scientific article; zbMATH DE number 4075830
• Rank functions of closure spaces of finite rank

Cited in

(5)

• Scalability and the isomorphism problem
• Recursion-theoretic ranking and compression
• Closure and nonclosure properties of the classes of compressible and rankable sets
• scientific article; zbMATH DE number 4204287 (Why is no real title available?)
• On the complexity of ranking

This page was built for publication: Closure and nonclosure properties of the compressible and rankable sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2278274)