Reducibilities on tally and sparse sets

DOI10.1051/ita/1991250302931zbMath0731.68039OpenAlexW52632172MaRDI QIDQ3357534

Ronald V. Book, Shouwen Tang

Publication date: 1991

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92394

zbMATH Keywords

sparse setscomplexity classestally setspolynomial-type computable reducibilities

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (4)

Degrees and reducibilities of easy tally sets ⋮ Upper bounds for the complexity of sparse and tally descriptions ⋮ Monotonous and randomized reductions to sparse sets ⋮ The structure of logarithmic advice complexity classes

Cites Work

• Unnamed Item
• Kolmogorov complexity and degrees of tally sets
• Strong nondeterministic polynomial-time reducibilities
• Complexity and structure
• Continuous optimization problems and a polynomial hierarchy of real functions
• A comparison of polynomial time reducibilities
• Sets with small generalized Kolmogorov complexity
• Distinguishing conjunctive and disjunctive reducibilities by sparse sets
• On Restricting the Size of Oracles Compared with Restricting Access to Oracles
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• On Sets Truth-Table Reducible to Sparse Sets
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• P-Printable Sets

This page was built for publication: Reducibilities on tally and sparse sets