Closure and Nonclosure Properties of the Compressible and Rankable Sets
Closure and Nonclosure Properties of the Compressible and Rankable Sets
复制标题
可压缩可排序集的闭包和非闭包性质
DOI：
10.1007/978-3-030-13435-8_13
复制
发表时间：
2016
影响因子：
4.7
通讯作者：
Daniel Rubery
中科院分区：
文献类型：
--
作者：
Jackson Abascal;L. Hemaspaandra;S. Maimon;Daniel Rubery
自从Allender[2]和Goldberg和Sipser[7]引入多项式时间排序的正式研究以来，可排序集和可压缩集已经被研究了超过四分之一个世纪。然而，即使经过了这么长时间，在最重要的布尔和其他操作下，可排序集和可压缩集是否封闭，基本上仍然没有被探索。本文从多项式时间理论和递归理论两方面研究了这些问题的压缩和排序，并对几乎每一种情况都得到了给定运算的闭、非闭或闭-已知复杂度-类-崩溃的结果。尽管压缩和排序类捕获了关于集合结构的一些非常自然的东西，但事实证明，它们在闭包属性方面非常脆弱，许多甚至不具备最基本的闭包属性。例如，我们证明了关于连接（又称不联合）操作：p -可排序集不闭合，半强p -可排序集是否闭合与\(\mathrm{P}= \text {UP}\cap \text {coUP}\)是否紧密相连，强p -可排序集是否闭合。
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 \(\mathrm{P}= \text {UP}\cap \text {coUP}\), and the strongly P-rankable sets are closed.