Closure and nonclosure properties of the classes of compressible and rankable sets
Closure and nonclosure properties of the classes of compressible and rankable sets
复制标题
可压缩集和可排序集类的闭包和非闭包性质
DOI：
10.1016/j.jcss.2021.02.004
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Rubery, Daniel
中科院分区：
文献类型：
--
作者：
Abascal, Jackson;Hemaspaandra, Lane A.;Maimon, Shir;Rubery, Daniel
对可排集和可压缩集的研究已经超过四分之一个世纪。我们问这些类是否在最重要的布尔运算和其他运算下是封闭的。对于多项式时间和递归理论的压缩和排序，我们都研究了这个问题，并且对于几乎每一种情况都得到了闭合、非闭合或Closed-Iff-Well-Known-Complexity-Classes-Collapse的结果。尽管压缩和排序类捕获了集合结构的一些非常自然的东西，但事实证明，这些类在闭包属性方面非常脆弱，许多类甚至无法拥有最基本的闭包属性。例如，对于并(又名不交并)运算：P-可秩集是不闭的，半强P-可秩集是否闭与P=Up∩政变密切相关，强P-可秩集是闭的。
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 P= UP∩ coUP, and the strongly P-rankable sets are closed.
登录
查看更多内容
影响因子：
1
作者：
Martínez, C;Molinero, X
通讯作者：
Molinero, X
DOI：
10.1145/22145.22194
发表时间：
1985-12
期刊：
SIAM J. Comput.
影响因子：
--
作者：
A. Goldberg;M. Sipser
通讯作者：
A. Goldberg;M. Sipser
计算上下文无关语言中给定长度字符串数量的复杂性
DOI：
10.1016/0304-3975(91)90023-u
发表时间：
1991
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
A. Bertoni;M. Goldwurm;N. Sabadini
通讯作者：
N. Sabadini
影响因子：
4.7
作者：
Jackson Abascal;L. Hemaspaandra;S. Maimon;Daniel Rubery
通讯作者：
Daniel Rubery
稀疏集、低度和高度
DOI：
10.1137/0215053
发表时间：
1986
期刊：
SIAM J. Comput.
影响因子：
--
作者：
J. Balcázar;R. V. Book;U. Schöning
通讯作者：
U. Schöning