Recursion-theoretic ranking and compression

作     者：Hemaspaandra, Lane A. Rubery, Daniel 

作者机构：Univ Rochester Dept Comp Sci 601 Elmwood Ave Rochester NY 14627 USA Google Inc 1600 Amphitheatre Pkwy Mountain View CA 94043 USA 

出 版 物：《JOURNAL OF COMPUTER AND SYSTEM SCIENCES》 (计算机与系统科学杂志)

年 卷 期：2019年第101卷

页      面：31-41页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NSF-CCF-1101479 

主　　题：Compression functions Ranking functions Perfect minimal hash functions Recursive function theory 

摘      要：For which sets A does there exist a mapping, computed by a total or partial recursive function, such that the mapping, when its domain is restricted to A, is a 1-to-1, onto mapping to Sigma*? For which sets A does there exist such a mapping that respects the lexicographical ordering within A? Both cases are types of perfect, minimal hash functions. The complexity-theoretic versions of these notions are known as compression functions and ranking functions. This paper defines and studies the recursion-theoretic versions of compression and ranking functions, and in particular studies which sets have, or lack, such functions. Thus this is a case where, in contrast to the usual direction of notion transferal, notions from complexity theory are inspiring notions, and an investigation, in computability theory. We show that the rankable and compressible sets broadly populate the 1-truth-table degrees, and we prove that every nonempty coRE cylinder is recursively compressible. (C) 2018 Elsevier Inc. All rights reserved.