On the coincidence of complexity classes BPC and TC^0

DOI10.3103/S0278641922040069MaRDI QIDQ6043894zbMATH OpenFDO

Authors Igor V. Savitskiy

Publication date 25 May 2023

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

Full work available at URL https://doi.org/10.3103/S0278641922040069

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites work

• Bases for \(\mathrm{AC}^{0}\) and other complexity classes
• Constant Depth Reducibility
• CRN elimination and substitution bases for complexity classes
• General recursive functions of natural numbers
• Generating some classes of recursive functions by superpositions of simple arithmetic functions
• 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?)
• On elementary word functions obtained by bounded prefix concatenation
• On uniformity within \(NC^ 1\)
• Uniform constant-depth threshold circuits for division and iterated multiplication.

Cited in

(1)

• On Tally Relativizations of $BP$-Complexity Classes

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

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