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

compression functions perfect minimal hash functions ranking functions recursive function theory

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) Analysis of algorithms and problem complexity (68Q25)

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

S i g m a^{*}

? 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.

Review text

This paper studies sets that can be compressed in an effective, but not necessarily efficient way. A set of strings \(A\) is recursively rankable if there exists a computable function \(f\) such that if the lexicogrpahical ordering of \(A\) is \(\{x_1 < x_2 < \dots \}\) then \(f(x_i)\) is the \(i\)-th string in the lexicographical ordering of the set of strings. A set of strings \(A\) is recursively computable if there exists a computable function \(f\) that maps bijectively \(A\) to the set of strings. The paper also defines the similar notions for \(f\) partially computable. The general flavor of results is that the effective compressibility and the effective rankability of a set \(A\) do not imply any bound on the position of \(A\) in the arithmetic hierarchy. For example, it is shown that every \(1\)-truth-table degree contains recursively rankable sets and recursively compressible sets.

Recommendations

Cites work

Cited in

(4)

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)