Recursion-theoretic ranking and compression
From MaRDI portal
Publication:1713478
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
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
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