On the coincidence of complexity classes BPC and \(\text{TC}^0 \)

DOI10.3103/s0278641922040069MaRDI QIDQ6043894

Igor V. Savitskiy

Publication date: 25 May 2023

Published in: Moscow University Computational Mathematics and Cybernetics (Search for Journal in Brave)

zbMATH Keywords

operation of bounded prefix concatenationclass \(\text{TC}^0 \)

Mathematics Subject Classification ID

Theory of computing (68Qxx) Proof theory and constructive mathematics (03Fxx) Computability and recursion theory (03Dxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On elementary word functions obtained by bounded prefix concatenation
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Generating some classes of recursive functions by superpositions of simple arithmetic functions
• On uniformity within \(NC^ 1\)
• General recursive functions of natural numbers
• Bases for AC0 and Other Complexity Classes
• CRN Elimination and Substitution Bases for Complexity Classes
• Constant Depth Reducibility

This page was built for publication: On the coincidence of complexity classes BPC and \(\text{TC}^0 \)