Recursion-theoretic ranking and compression

DOI10.1016/J.JCSS.2018.10.003MaRDI QIDQ1713478zbMATH OpenOpenAlexFDO

Authors Daniel Rubery, Lane A. Hemaspaandra

Publication date 25 January 2019

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

ranking functionsrecursive function theorycompression functionsperfect minimal hash functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Other degrees and reducibilities in computability and recursion theory (03D30)

Abstract: 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 $Sigm{a}^{\ast }$? And 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. The present paper defines and studies the recursion-theoretic versions of compression and ranking functions, and in particular studies the question of 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.

Recommendations

• Compression and Ranking
• Closure and nonclosure properties of the compressible and rankable sets
• Recursively compressible sets
• Closure and nonclosure properties of the classes of compressible and rankable sets
• On the complexity of ranking

Cites work

• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 1482586 (Why is no real title available?)
• scientific article; zbMATH DE number 3273186 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• A comparison of polynomial time reducibilities
• A very hard log-space counting class
• Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
• Bi-immune sets for complexity classes
• Classical recursion theory. Vol. II
• Compression and Ranking
• Creative sets
• Easy sets and hard certificate schemes
• Inverting onto functions.
• On definable sets of positive integers
• On simple and creative sets in NP
• On the complexity of ranking
• Oracle-dependent properties of the lattice of NP sets
• Polynomial-time compression
• Recursive Predicates and Quantifiers
• Recursively enumerable sets of positive integers and their decision problems
• Retraceable Sets
• Scalability and the isomorphism problem
• The complexity of finding top-Toda-equivalence-class members
• The complexity of ranking simple languages
• The polynomial-time hierarchy

Cited in

(3)

• Compression and Ranking
• Closure and nonclosure properties of the classes of compressible and rankable sets
• On the complexity of ranking

This page was built for publication: Recursion-theoretic ranking and compression

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