Reducibilities on tally and sparse sets

DOI10.1051/ITA/1991250302931MaRDI QIDQ3357534zbMATH OpenOpenAlexFDO

Authors Shouwen Tang, Ronald V. Book

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

complexity classespolynomial-type computable reducibilitiessparse setstally sets

Mathematics Subject Classification ID

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

Cites work

• A comparison of polynomial time reducibilities
• Complexity and structure
• Continuous optimization problems and a polynomial hierarchy of real functions
• Distinguishing conjunctive and disjunctive reducibilities by sparse sets
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• Kolmogorov complexity and degrees of tally sets
• On Restricting the Size of Oracles Compared with Restricting Access to Oracles
• On Sets Truth-Table Reducible to Sparse Sets
• P-Printable Sets
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Sets with small generalized Kolmogorov complexity
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Strong nondeterministic polynomial-time reducibilities

Cited in

(6)

• The structure of logarithmic advice complexity classes
• Sparse selfreducible sets and nonuniform lower bounds
• Monotonous and randomized reductions to sparse sets
• Upper bounds for the complexity of sparse and tally descriptions
• On sparseness and Turing reducibility over the reals
• Degrees and reducibilities of easy tally sets

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

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