Degrees and reducibilities of easy tally sets

DOI10.1007/3-540-58338-6_87MaRDI QIDQ5096899zbMATH OpenOpenAlexFDO

Authors M. Hermo

Publication date 18 August 2022

Published in Mathematical Foundations of Computer Science 1994 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-58338-6_87

Mathematics Subject Classification ID

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

Recommendations

• The structure of logarithmic advice complexity classes
• scientific article; zbMATH DE number 4079403
• scientific article; zbMATH DE number 4075037
• Polynomial-time reducibilities and ``almost all oracle sets
• CONJUNCTIVE AND DISJUNCTIVE REDUCIBILITIES TO SPARSE AND TALLY SETS REVISITED

Cites work

• Continuous optimization problems and a polynomial hierarchy of real functions
• scientific article; zbMATH DE number 3978383 (Why is no real title available?)
• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• Kolmogorov complexity and degrees of tally sets
• Logarithmic advice classes
• On helping by robust oracle machines
• On Sets Truth-Table Reducible to Sparse Sets
• P-Printable Sets
• Reducibilities on tally and sparse sets
• Sets with small generalized Kolmogorov complexity
• The structure of logarithmic advice complexity classes

Cited in

(1)

• The structure of logarithmic advice complexity classes

This page was built for publication: Degrees and reducibilities of easy tally sets

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