New substitution bases for complexity classes

DOI10.1002/malq.201800055zbMath1455.03051OpenAlexW2996222520MaRDI QIDQ5112387

Stefano 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)

Cites Work

• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Generating some classes of recursive functions by superpositions of simple arithmetic functions
• Elimination of recursion schemas in the Grzegorczyk \(\mathcal{E}^2\) class
• Bases for AC0 and Other Complexity Classes
• CRN Elimination and Substitution Bases for Complexity Classes
• Function Algebras on Finite Sets
• An example of a simple quasi-universal function in the class ε 2 of the Grzegorczyk hierarchy
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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