New substitution bases for complexity classes

DOI10.1002/MALQ.201800055MaRDI QIDQ5112387zbMATH OpenOpenAlexFDO

Authors S. Mazzanti

Publication date 29 May 2020

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/11578/286521

zbMATH Keywords

circuit complexitycomplexity classesfunction classessubstitution basis

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Bases for \(\mathrm{AC}^{0}\) and other complexity classes
• scientific article; zbMATH DE number 1390027
• CRN elimination and substitution bases for complexity classes
• scientific article; zbMATH DE number 1018349
• Tailoring recursion for complexity

Cites work

• An example of a simple quasi-universal function in the class ε 2 of the Grzegorczyk hierarchy
• Bases for \(\mathrm{AC}^{0}\) and other complexity classes
• CRN elimination and substitution bases for complexity classes
• Elimination of recursion schemas in the Grzegorczyk \(\mathcal{E}^2\) class
• Function Algebras on Finite Sets
• Generating some classes of recursive functions by superpositions of simple arithmetic functions
• scientific article; zbMATH DE number 4134023 (Why is no real title available?)
• scientific article; zbMATH DE number 176199 (Why is no real title available?)
• scientific article; zbMATH DE number 806747 (Why is no real title available?)
• scientific article; zbMATH DE number 1390027 (Why is no real title available?)
• scientific article; zbMATH DE number 3353255 (Why is no real title available?)
• Plain bases for classes of primitive recursive functions
• Uniform constant-depth threshold circuits for division and iterated multiplication.

Cited in

(3)

• Bases for \(\mathrm{AC}^{0}\) and other complexity classes
• CRN elimination and substitution bases for complexity classes
• Iteration on notation and unary functions

This page was built for publication: New substitution bases for complexity classes

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