Recursion-theoretic ranking and compression

DOI10.1016/j.jcss.2018.10.003zbMath1459.03059arXiv1610.01185OpenAlexW2963476850MaRDI QIDQ1713478

Daniel Rubery, Hemaspaandra, Lane A.

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)

Related Items

Closure and nonclosure properties of the classes of compressible and rankable sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Oracle-dependent properties of the lattice of NP sets
• On the complexity of ranking
• On simple and creative sets in NP
• Polynomial-time compression
• A very hard log-space counting class
• A comparison of polynomial time reducibilities
• The polynomial-time hierarchy
• Classical recursion theory. Vol. II
• Scalability and the isomorphism problem
• Easy sets and hard certificate schemes
• Inverting onto functions.
• The complexity of finding top-Toda-equivalence-class members
• The complexity of ranking simple languages
• Retraceable Sets
• Bi-immune sets for complexity classes
• Compression and Ranking
• Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
• On definable sets of positive integers
• Recursive Predicates and Quantifiers
• Recursively enumerable sets of positive integers and their decision problems
• Creative sets