TC0

A Boolean circuit family is a sequence of Boolean circuits $C\_1,\; C\_2,\; C\_3,\; \backslash dots$ consisting of a feedforward network of Boolean functions. A binary language $L\; \backslash in\; 2^*$ is in the TC⁰ class if there exists a Boolean circuit family $C\_1,\; C\_2,\; C\_3,\; \backslash dots$, such that

• There exists a polynomial function $p$, and a constant $d$.
• Each $C\_n$ is composed of up to $p(n)$ unbounded fan-in AND, OR, NOT, and MAJ gates in up to $d$ layers.
• For each $x\; \backslash in\; 2^n$, we have $x\; \backslash in\; L$ iff $C\_n(x)\; =\; 1$.

File:Artificial_neuron_structure.svg

Equivalently, instead of majority gates, we can use threshold gates with integer weights and thresholds, bounded by a polynomial. A threshold gate with $k$ inputs is defined by a list of weights $w\_1,\; \backslash dots,\; w\_k$ and a single threshold $\backslash theta$. Upon binary inputs $x\_1,\; \backslash dots,\; x\_k$, it outputs $+1$ if $\backslash sum\_i\; w\_i\; x\_k\; >\; \backslash theta$, else it outputs $-1$. A threshold gate is also called an artificial neuron.

Given a Boolean circuit with AND, OR, NOT, and threshold gates whose weights and thresholds are bounded within $[-M,\; +M]$, If we also provide the network with negations of binary inputs: $\backslash neg\; x\_1,\; \backslash dots,\; \backslash neg\; x\_k$, then we can convert the network to one that computes the same input-output function using only AND, OR, and threshold gates, with the same depth, at most double the number of gates in each layer, weights bounded within $[0,\; +M]$, and thresholds bounded within $[-M,\; +M]$. Therefore, TC⁰ can be defined equivalently as the languages decidable by some Boolean circuit family $C\_1,\; C\_2,\; C\_3,\; \backslash dots$ such that

• There exists a polynomial function $p$, and a constant $d$.
• Each $C\_n$ is composed of up to $p(n)$ threshold gates in up to $d$ layers, whose weights are non-negative integers, thresholds are integers, and both weights and thresholds are bounded within $\backslash pm\; p(n)$.
• For each $x\; \backslash in\; 2^n$, we have $x\; \backslash in\; L$ iff $C\_n(x)\; =\; 1$.

In this article, we by default consider Boolean circuits with a polynomial number of AND, OR, NOT, and threshold gates, with polynomial bound on integer weights and thresholds. The polynomial bound on weights and thresholds can be relaxed without changing the class $\backslash mathsf\{TC\}^0$.

In arithmetic circuit complexity theory, $\backslash mathsf\{TC\}^0$ can be equivalently characterized as the class of languages defined as the images of $\backslash mathrm\{sign\}\; \backslash circ\; f\_n$, where each $f\_n\; :\; \backslash \{0,\; 1\; \backslash \}^n\; \backslash to\; \backslash Z$ is computed by a polynomial-size constant-depth unbounded-fan-in arithmetic circuits with + and × gates, and constants from $\backslash \{-1,\; 0,\; +1\backslash \}$.{{Cite journal |last1=Agrawal |first1=Manindra |last2=Allender |first2=Eric |last3=Datta |first3=Samir |date=April 2000 |title=On TC0, AC0, and Arithmetic Circuits |url=https://linkinghub.elsevier.com/retrieve/pii/S0022000099916756 |journal=Journal of Computer and System Sciences |language=en |volume=60 |issue=2 |pages=395–421 |doi=10.1006/jcss.1999.1675}}

{{unsolved|computer science|$\backslash mathsf\{TC\}^0\; \backslash overset\{?\}\{=\}\; \backslash mathsf\{NC\}^1$}}

We can relate TC⁰ to other circuit classes, including AC⁰ and NC¹ as follows:{{cite book | last=Vollmer | first=Heribert | title=Introduction to circuit complexity. A uniform approach | series=Texts in Theoretical Computer Science | location=Berlin | publisher=Springer-Verlag | year=1998 | isbn=3-540-64310-9 | zbl=0931.68055 | url=https://books.google.com/books?id=55ZTgOJs8bsC|page=126}}

$\backslash mathsf\{AC\}^0\; \backslash subsetneq\; \backslash mathsf\{AC\}^0[p]\; \backslash subsetneq\; \backslash mathsf\{TC\}^0\; \backslash subseteq\; \backslash mathsf\{NC\}^1.$

Whether $\backslash mathsf\{TC\}^0\; \backslash subseteq\; \backslash mathsf\{NC\}^1$

is a strict inclusion is "one of the main open problems in circuit complexity". In fact, it is even open whether $\backslash mathsf\{TC\}^0\; \backslash subseteq\; \backslash mathsf\{P/poly\}$

is a strict inclusion! This is in some sense unsurprising, since there is no natural proof for $\backslash mathsf\{TC\}^0\; \backslash subsetneq\; \backslash mathsf\{P/poly\}$

, assuming that there is a cryptographically secure pseudorandom number generator in $\backslash mathsf\{TC\}^0$

, which have been explicitly constructed under the assumption that factoring Blum integers is hard (i.e. requires circuits of size $2^\{\backslash mathsf\{poly\}(n)\}$), which is widely suspected to be true.{{Cite journal |last1=Naor |first1=Moni |last2=Reingold |first2=Omer |date=March 2004 |title=Number-theoretic constructions of efficient pseudo-random functions |url=https://dl.acm.org/doi/10.1145/972639.972643 |journal=Journal of the ACM |language=en |volume=51 |issue=2 |pages=231–262 |doi=10.1145/972639.972643 |issn=0004-5411}} More generally, randomness and hardness for have been shown to be closely related.{{Cite book |last1=Hatami |first1=Pooya |last2=Hoza |first2=William M. |last3=Tal |first3=Avishay |last4=Tell |first4=Roei |chapter=Fooling Constant-Depth Threshold Circuits (Extended Abstract) |date=February 2022 |title=2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) |chapter-url=https://par.nsf.gov/servlets/purl/10384268 |publisher=IEEE |pages=104–115 |doi=10.1109/FOCS52979.2021.00019 |isbn=978-1-6654-2055-6}} It is also an open question whether $\backslash mathsf\{NEXP\}\; \backslash subseteq\; \backslash mathsf\{TC\}^0$

. Indeed, $\backslash mathsf\{NEXP\}\; \backslash not\backslash subseteq\; \backslash mathsf\{ACC\}^0$

was only proven in 2011.{{Cite book |last=Williams |first=Ryan |chapter=Non-uniform ACC Circuit Lower Bounds |date=June 2011 |title=2011 IEEE 26th Annual Conference on Computational Complexity |chapter-url=https://ieeexplore.ieee.org/document/5959801 |pages=115–125 |doi=10.1109/CCC.2011.36|isbn=978-1-4577-0179-5 }}

Note that because non-uniform $\backslash mathsf\{TC\}^0$

and $\backslash mathsf\{ACC\}^0$

can compute functions that are not Turing-computable, it is certainly the case that $\backslash mathsf\{TC\}^0\; \backslash not\backslash subseteq\; \backslash mathsf\{NEXP\}$

and $\backslash mathsf\{ACC\}^0\; \backslash not\backslash subseteq\; \backslash mathsf\{NEXP\}$

. The 2011 result simply shows that $\backslash mathsf\{ACC\}^0$

and $\backslash mathsf\{NEXP\}$

are incomparable classes. The open question is whether $\backslash mathsf\{TC\}^0$

and $\backslash mathsf\{NEXP\}$

are incomparable as well.

Note that, while the time hierarchy theorem proves that $\backslash mathsf\{NP\}\; \backslash subsetneq\; \backslash mathsf\{NEXP\}$

, both complexity classes are uniform, meaning that a single Turing machine is responsible for solving the problem at any input length. In contrast, a $\backslash mathsf\{TC\}^0$

circuit family may be non-uniform, meaning that there may be no good algorithm for finding the correct circuit, other than exhaustive search over all $2^\{\backslash mathsf\{poly\}(n)\}$

possible Boolean circuits of bounded depth and $\backslash mathsf\{poly\}(n)$

size, then checking all $2^n$ possible inputs to verify that the circuit is correct.

It has been proven that if $\backslash mathsf\{TC\}^0\; =\; \backslash mathsf\{NC\}^1$, then any $\backslash epsilon\; >\; 0$, there exists a $\backslash mathsf\{TC\}^0$

circuit family of gate number $O(n^\{1+\backslash epsilon\})$ that solves the Boolean Formula Evaluation problem. Thus, any superlinear bound suffices to prove $\backslash mathsf\{TC\}^0\; \backslash neq\; \backslash mathsf\{NC\}^1$.{{Cite journal |last1=Allender |first1=Eric |last2=Koucký |first2=Michal |date=March 2010 |title=Amplifying lower bounds by means of self-reducibility |url=https://dl.acm.org/doi/10.1145/1706591.1706594 |journal=Journal of the ACM |language=en |volume=57 |issue=3 |pages=1–36 |doi=10.1145/1706591.1706594 |issn=0004-5411}}

DLOGTIME-uniform $\backslash mathsf\{TC\}^0$

is also known as $\backslash mathsf\{FOM\}$

, because it is equivalent to first-order logic with Majority quantifiers.{{Cite journal |last1=Mix Barrington |first1=David A. |last2=Immerman |first2=Neil |last3=Straubing |first3=Howard |date=1990-12-01 |title=On uniformity within NC1 |url=https://dx.doi.org/10.1016/0022-0000%2890%2990022-D |journal=Journal of Computer and System Sciences |volume=41 |issue=3 |pages=274–306 |doi=10.1016/0022-0000(90)90022-D |issn=0022-0000}} Specifically, given a logic formula that takes $x\_1,\; x\_2,\; \backslash dots,\; x\_n$ Boolean variables, a Majority quantifier $M$ is used as follows: given a formula with exactly one free variable $\backslash phi(x)$, the quantified $Mx\; \backslash phi(x)$ is true iff $\backslash phi(x\_i)$ is true for over half of $i\; \backslash in\; 1:n$, Integer division (given $x,\; y$ $n$-bit integers, find $\backslash lfloor\; x/y\backslash rfloor$), powering (given $x$ an $n$-bit integer, and $k$ a $O(\backslash ln(n))$-bit integer, find $x^k$), and iterated multiplication (multiplying $n$ of $n$-bit integers) are all in DLOGTIME-uniform $\backslash mathsf\{TC\}^0$

.{{Citation |last=Hesse |first=William |title=Division Is In Uniform TC0 |date=2001 |work=Automata, Languages and Programming |series=Lecture Notes in Computer Science |volume=2076 |pages=104–114 |editor-last=Orejas |editor-first=Fernando |url=https://link.springer.com/chapter/10.1007/3-540-48224-5_9 |access-date=2025-03-19 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |language=en |doi=10.1007/3-540-48224-5_9 |isbn=978-3-540-42287-7 |editor2-last=Spirakis |editor2-first=Paul G. |editor3-last=van Leeuwen |editor3-first=Jan}} It is usually considered the appropriate level of uniformity for $\backslash mathsf\{TC\}^0$

, neither too strong nor too weak. Specifically, because P is usually suspected to be stronger than $\backslash mathsf\{TC\}^0$

, while DLOGTIME is suspected to be equivalent in strength in some sense, DLOGTIME-uniformity is usually assumed, when uniformity is considered for $\backslash mathsf\{TC\}^0$

.{{Cite journal |last1=Santhanam |first1=Rahul |last2=Williams |first2=Ryan |date=2014-06-01 |title=On Uniformity and Circuit Lower Bounds |url=https://link.springer.com/article/10.1007/s00037-014-0087-y |journal=Computational Complexity |language=en |volume=23 |issue=2 |pages=177–205 |doi=10.1007/s00037-014-0087-y |issn=1420-8954|hdl=20.500.11820/d254202f-5539-45ba-ba25-cfe680aa46e9 |hdl-access=free }}

The permanent of a 0-1 matrix is not in uniform $\backslash mathsf\{TC\}^0$

.{{Cite journal |last=Allender |first=Eric |date=1999 |title=The permanent requires large uniform threshold circuits |url=http://cjtcs.cs.uchicago.edu/articles/1999/7/contents.html |journal=Chicago Journal of Theoretical Computer Science |language=en |volume=5 |issue=1 |pages=1–19 |doi=10.4086/cjtcs.1999.007 |issn=1073-0486}}

Uniform $\backslash mathsf\{TC\}^0\; \backslash subsetneq\; \backslash mathsf\{PP\}$.{{cite book | first=E. | last=Allender | chapter= A note on uniform circuit lower bounds for the counting hierarchy | title=Proceedings 2nd International Computing and Combinatorics Conference (COCOON) | volume=1090 | series=Springer Lecture Notes in Computer Science | pages=127–135 | year=1996 }} As cited in {{cite journal | last1 = Burtschick | first1 = Hans-Jörg | last2 = Vollmer | first2 = Heribert | doi = 10.1142/S0129054198000180 | id = {{ECCC|1996|96|005}} | issue = 3 | journal = International Journal of Foundations of Computer Science | pages = 277–294 | title = Lindström quantifiers and leaf language definability | volume = 9 | year = 1998}}

The functional version of the uniform TC⁰ coincides with the closure with respect to composition of the projections and one of the following function sets $\backslash \{n+m,\; n\; \backslash ,\backslash stackrel\{.\}\{-\}\backslash ,\; m,\; n\backslash wedge\; m,\; \backslash lfloor\; n/m\; \backslash rfloor,\; 2^\{\backslash lfloor\; \backslash log\_2\; n\; \backslash rfloor^2\}\; \backslash \}$, $\backslash \{n+m,\; n\; \backslash ,\backslash stackrel\{.\}\{-\}\backslash ,\; m,\; n\backslash wedge\; m,\; \backslash lfloor\; n/m\; \backslash rfloor,\; n^\{\backslash lfloor\; \backslash log\_2\; m\; \backslash rfloor\}\; \backslash \}$.{{cite arXiv |eprint=1611.04843 |class=cs.CC |first=Sergey. |last=Volkov |title=Finite Bases with Respect to the Superposition in Classes of Elementary Recursive Functions, dissertation |year=2016}} Here $n\; \backslash ,\backslash stackrel\{.\}\{-\}\backslash ,\; m=\backslash max(0,n-m)$, $n\backslash wedge\; m$ is a bitwise AND of $n$ and $m$. By functional version one means the set of all functions $f(x\_1,\backslash ldots,x\_n)$ over non-negative integers that are bounded by functions of FP and $(y\backslash text\{-th\; bit\; of\; \}f(x\_1,\backslash ldots,x\_n))$ is in the uniform TC⁰.

TC⁰ can be divided further, into a hierarchy of languages requiring up to 1 layer, 2 layers, etc. Let $\backslash mathsf\{TC\}^0\_d$ be the class of languages decidable by a threshold circuit family of up to depth $d$:$$\backslash mathsf\{TC\}^0\_1\; \backslash subset\; \backslash mathsf\{TC\}^0\_2\; \backslash subset\; \backslash cdots\; \backslash subset\; \backslash mathsf\{TC\}^0\; =\; \backslash bigcup\_\{d=1\}^\backslash infty\; \backslash mathsf\{TC\}^0\_d$$The hierarchy can be even more finely divided.

The MAJ gate is sometimes called an unweighted threshold gate. They are equivalent up to a uniform polynomial overhead. In detail:

• A MAJ gate is a threshold gate where all the weights are 1, and threshold is $1/2$ the fan-in.
• A polynomial-size circuit containing threshold gates with polynomial integer weights and threshold can be converted to a polynomial-size circuit with the same depth. Specifically, the weights can be simulated by replicating the input circuits, and the threshold can be simulated by replicating constant True/False inputs.

Furthermore, there is an explicit algorithm, by which, given a single $n$-input threshold gate with arbitrary (unbounded) integer weights and thresholds, it constructs a depth-2 circuit using $\backslash mathsf\{poly\}(n)$-many AND, OR, NOT, and MAJ gates. Thus, any polynomial-size, depth-$d$ threshold circuit can be simulated uniformly by a polynomial-size majority circuit of depth $d+1$.{{Cite journal |last1=Goldmann |first1=Mikael |last2=Håstad |first2=Johan |last3=Razborov |first3=Alexander |date=1992-12-01 |title=Majority gates vs. general weighted threshold gates |url=https://link.springer.com/article/10.1007/BF01200426 |journal=Computational Complexity |language=en |volume=2 |issue=4 |pages=277–300 |doi=10.1007/BF01200426 |issn=1420-8954}}{{Cite journal |last1=Goldmann |first1=Mikael |last2=Karpinski |first2=Marek |date=February 1998 |title=Simulating Threshold Circuits by Majority Circuits |url=http://epubs.siam.org/doi/10.1137/S0097539794274519 |journal=SIAM Journal on Computing |language=en |volume=27 |issue=1 |pages=230–246 |doi=10.1137/S0097539794274519 |issn=0097-5397}}

As a separation theorem, it is known that the $n$

-input Boolean inner product function (IP), defined below, is computable by a majority circuit with 3 layers and $O(n)$

gates, but is not computable by a threshold circuit with 2 layers and $\backslash mathsf\{poly\}(n)$

gates.{{Pg|location=Section 11.10.2}}

For any fixed $n$, because there are only finitely many Boolean functions that can be computed by a threshold logic unit, it is possible to set all $w\_1,\; \backslash dots,\; w\_n,\; \backslash theta$ to be integers. Let $W(n)$ be the smallest number $W$ such that every possible real threshold function of $n$ variables can be realized using integer weights of absolute value $\backslash leq\; W$. It is known that{{Cite journal |last1=Alon |first1=Noga |last2=Vũ |first2=Văn H |date=1997-07-01 |title=Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs |url=https://linkinghub.elsevier.com/retrieve/pii/S0097316597927801 |journal=Journal of Combinatorial Theory, Series A |volume=79 |issue=1 |pages=133–160 |doi=10.1006/jcta.1997.2780 |issn=0097-3165}}$$\backslash frac\; 12\; n\; \backslash log\; n\; -\; 2n\; +\; o(n)\; \backslash leq\; \backslash log\_2\; W(n)\; \backslash leq\; \backslash frac\; 12\; n\; \backslash log\; n\; -\; n\; +\; o(n)$$See {{Cite book |last=Jukna |first=Stasys |title=Boolean Function Complexity: Advances and Frontiers |date=2012 |publisher=Springer Berlin Heidelberg |isbn=978-3-642-24507-7 |series=Algorithms and Combinatorics |location=Berlin, Heidelberg}}{{Pg|location=Section 11.10}} for a literature review.

Sometimes the class of polynomial-bounded weights and thresholds with depth $d$ is denoted as $\backslash widehat\{\backslash mathsf\{LT\}\}\_d\; :=\; \backslash mathsf\{TC\}\_d^0$, and $\backslash mathsf\{LT\}\_d$ denotes the class where the weight and thresholds are unbounded ("large weight threshold circuit"). This formalizes neural networks with real-valued activation functions.{{Cite journal |last1=Šíma |first1=Jiří |last2=Orponen |first2=Pekka |date=2003-12-01 |title=General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results |url=https://direct.mit.edu/neco/article/15/12/2727-2778/6791 |journal=Neural Computation |language=en |volume=15 |issue=12 |pages=2727–2778 |doi=10.1162/089976603322518731 |pmid=14629867 |issn=0899-7667}}

As previously stated, any polynomial-size, depth-$d$ threshold circuit can be simulated uniformly by a polynomial-size majority circuit of depth $d+1$. Therefore, $\backslash mathsf\{TC\}\_d^0\; \backslash subset\; \backslash mathsf\{LT\}\_d\; \backslash subset\; \backslash mathsf\{TC\}\_\{d+1\}^0$. It has been proven that $\backslash mathsf\{TC\}\_2^0\; \backslash subsetneq\; \backslash mathsf\{LT\}\_2$.

Allowing the sigmoid activation function $\backslash sigma$ does not increase the power, that is, $\backslash mathsf\{TC\}\_d^0\; =\; \backslash mathsf\{TC\}\_d^0(\backslash sigma)$ for all $d\; \backslash geq\; 1$, assuming the weights are polynomially bounded.{{Cite book |last1=Maass |first1=W. |last2=Schnitger |first2=G. |last3=Sontag |first3=E.D. |chapter=On the computational power of sigmoid versus Boolean threshold circuits |date=1991 |title=[1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science |chapter-url=https://ieeexplore.ieee.org/document/185447 |publisher=IEEE Comput. Soc. Press |pages=767–776 |doi=10.1109/SFCS.1991.185447 |isbn=978-0-8186-2445-2}}

Like how the P class has a probabilistic version BPP, the $\backslash mathsf\{TC\}^0$ has a probabilistic version $\backslash mathsf\{RTC\}^0$. It is defined as the class of languages that can be polynomial-probabilistically decided.

Let $C\_1,\; C\_2,\; C\_3,\; \backslash dots$ be a Boolean circuit family that takes two kinds of inputs. A given circuit $C\_n$ takes the deterministic inputs $x\_1,\; \backslash dots,\; x\_n$, and the random inputs $y\_1,\; \backslash dots,\; y\_m$, where $m\; =\; \backslash mathsf\{poly\}(n)$. The random inputs are sampled uniformly over all $2^m$ possibilities.

A language $L\; \backslash subset\; 2^*$ is decided polynomial-probabilistically by the family if for each $x\; \backslash in\; 2^n$, if $x\; \backslash in\; L$, then the probability that $C\_n(x,\; y)\; =\; +1$ is at least $\backslash frac\; 12\; +\; \backslash frac\{1\}\{\backslash mathsf\{poly\}(n)\}$, and if $x\; \backslash not\backslash in\; L$, then the probability that $C\_n(x,\; y)\; =\; +1$ is at most $\backslash frac\; 12\; -\; \backslash frac\{1\}\{\backslash mathsf\{poly\}(n)\}$.

Similarly, (feedforward) Boltzmann machines have been modelled as $\backslash mathsf\{RTC\}^0$ circuits with boundedly-unreliable threshold units. That is, each threshold unit may, independently at random, with a bounded probability , make the wrong output.{{Cite journal |last1=Parberry |first1=Ian |last2=Schnitger |first2=Georg |date=1989-01-01 |title=Relating Boltzmann machines to conventional models of computation |url=https://www.sciencedirect.com/science/article/abs/pii/0893608089900154 |journal=Neural Networks |volume=2 |issue=1 |pages=59–67 |doi=10.1016/0893-6080(89)90015-4 |issn=0893-6080}}

Sometimes, this class is also called $\backslash mathsf\{BPTC\}^0$, in a closer analogy with BPP. In this definition, the probability that $C\_n(x,\; y)\; =\; +1$ is at least $\backslash frac\; 23$, and if $x\; \backslash not\backslash in\; L$, then the probability that $C\_n(x,\; y)\; =\; +1$ is at most $\backslash frac\; 13$. By the standard trick of sampling many times then taking the majority opinion, any $d$-layer $\backslash mathsf\{RTC\}^0$ circuit can be converted to a $(d+1)$-layer $\backslash mathsf\{BPTC\}^0$ circuit.

Analogous to how $\backslash mathsf\{TC\}^0\_1\; \backslash subset\; \backslash mathsf\{TC\}^0\_2\; \backslash subset\; \backslash cdots\; \backslash subset\; \backslash mathsf\{TC\}^0\; =\; \backslash bigcup\_\{d=1\}^\backslash infty\; \backslash mathsf\{TC\}^0\_d$, $\backslash mathsf\{RTC\}^0$ can also be divided into$$\backslash mathsf\{RTC\}^0\_1\; \backslash subset\; \backslash mathsf\{RTC\}^0\_2\; \backslash subset\; \backslash cdots\; \backslash subset\; \backslash mathsf\{RTC\}^0\; =\; \backslash bigcup\_\{d=1\}^\backslash infty\; \backslash mathsf\{RTC\}^0\_d$$By definition, $\backslash mathsf\{TC\}^0\_d\; \backslash subset\; \backslash mathsf\{RTC\}^0\_d$. Furthermore, since $\backslash mathsf\{RTC\}^0\_d\; \backslash subset\; \backslash mathsf\{TC\}^0\_\{d+1\}$, there is a full hierarchy: $$\backslash mathsf\{TC\}^0\_1\; \backslash subset\; \backslash mathsf\{RTC\}^0\_1\; \backslash subset\; \backslash mathsf\{TC\}^0\_\{2\}\; \backslash subset\; \backslash mathsf\{RC\}^0\_\{2\}\; \backslash subset\; \backslash cdots\; \backslash subset\; \backslash mathsf\{TC\}^0\; =\; \backslash mathsf\{RTC\}^0$$Similarly, allowing boundedly-unreliable threshold units, a $\backslash mathsf\{RTC\}^0\_d$ circuit can be converted to a $\backslash mathsf\{TC\}^0\_\{d+1\}$ circuit by running several copies of the original circuit in parallel, each with a fixed choice for the random inputs (a hardcoded advice), and then taking a Majority over their outputs. That at least one advice exists is proven by Hoeffding's inequality, with essentially the same argument as the median trick. This argument is merely an existence proof, and thus not uniform in a way that matters for $\backslash mathsf\{TC\}^0$, since it gives no algorithm for discovering the advice other than brute-force enumeration.

Similarly, $\backslash mathsf\{RTC\}^0\; /\; \backslash mathsf\{poly\}\; =\; \backslash mathsf\{TC\}^0\; /\; \backslash mathsf\{poly\}$.{{Cite book |last1=Ajtai |first1=Miklos |last2=Ben-Or |first2=Michael |chapter=A theorem on probabilistic constant depth Computations |date=1984 |title=Proceedings of the sixteenth annual ACM symposium on Theory of computing - STOC '84 |chapter-url=http://portal.acm.org/citation.cfm?doid=800057.808715 |language=en |publisher=ACM Press |pages=471–474 |doi=10.1145/800057.808715 |isbn=978-0-89791-133-7}}

Let $\backslash oplus$ be defined as the parity function, or the XOR function. Then the following two separations are theorems:

• $\backslash mathsf\{RTC\}^0\_\{1\}\; \backslash subsetneq\; \backslash mathsf\{TC\}^0\_\{2\}$: The PARITY function $\backslash oplus$ is in $\backslash mathsf\{TC\}^0\_\{2\}$, but not in $\backslash mathsf\{RTC\}^0\_1$.
• $\backslash mathsf\{TC\}^0\_\{2\}\; \backslash subsetneq\; \backslash mathsf\{RTC\}^0\_\{2\}$: The Boolean inner product function (IP) is in $\backslash mathsf\{RTC\}^0\_\{2\}$ but not in $\backslash mathsf\{TC\}^0\_\{2\}$, where $$\backslash mathrm\{IP\}\_n\backslash left(x\_1,\; \backslash ldots,\; x\_n,\; x\_1^\{\backslash prime\},\; \backslash ldots,\; x\_n^\{\backslash prime\}\backslash right)=\backslash bigoplus\_\{i=1\}^n\; \backslash mathrm\{AND\}\backslash left(x\_i,\; x\_i^\{\backslash prime\}\backslash right)$$

The inner product function falls outside $\backslash mathsf\{TC\}^0\_\{2\}$ in a precise sense:{{Pg|location=Section 11.10.2}}

• If the weights of the bottom gates of a threshold circuit of depth 2 computing $\backslash mathrm\{IP\}\_n$ are polynomial, then for any $\backslash epsilon\; >\; 0$, for all large enough $n$, $\backslash mathrm\{IP\}\_n$ requires $\backslash geq\; 2^\{(1/2\; -\; \backslash epsilon)n\}$ gates.
• If the weights of the top gate in a threshold circuit of depth 2 computing $\backslash mathrm\{IP\}\_n$ are at most $2^\{o\backslash left(n^\{1\; /\; 3\}\backslash right)\}$, then the top gate must have fanin at least $2^\{\backslash Omega\backslash left(n^\{1\; /\; 3\}\backslash right)\}$.{{Cite journal |last1=Hajnal |first1=András |last2=Maass |first2=Wolfgang |last3=Pudlák |first3=Pavel |last4=Szegedy |first4=Márió |last5=Turán |first5=György |date=April 1993 |title=Threshold circuits of bounded depth |url=https://linkinghub.elsevier.com/retrieve/pii/002200009390001D |journal=Journal of Computer and System Sciences |language=en |volume=46 |issue=2 |pages=129–154 |doi=10.1016/0022-0000(93)90001-D}}
• If the weights of the bottom gates of a threshold circuit of depth 2 computing $\backslash mathrm\{IP\}\_n$ do not exceed $2^\{n\; /\; 3\}$, then the top gate must have fanin at least $2^\{\backslash Omega(n)\}$.{{Citation |last1=Forster |first1=Jürgen |title=Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity |date=2001 |work=FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science |volume=2245 |pages=171–182 |editor-last=Hariharan |editor-first=Ramesh |url=http://link.springer.com/10.1007/3-540-45294-X_15 |access-date=2025-03-19 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |doi=10.1007/3-540-45294-x_15 |isbn=978-3-540-43002-5 |last2=Krause |first2=Matthias |last3=Lokam |first3=Satyanarayana V. |last4=Mubarakzjanov |first4=Rustam |last5=Schmitt |first5=Niels |last6=Simon |first6=Hans Ulrich |editor2-last=Vinay |editor2-first=V. |editor3-last=Mukund |editor3-first=Madhavan}}

It is an open question how many levels the hierarchy has. It is also an open question whether the hierarchy collapses, that is, $\backslash mathsf\{TC\}^0\; =\; \backslash mathsf\{TC\}^0\_\{3\}$. In fact, there is still no exponential lower bound for $\backslash mathsf\{LT\}^0\_\{2\}$. Therefore, a fortiori, there is still no exponential lower bound for depth-3 polynomial-size majority circuits. There are exponential lower bounds if further restrictions are imposed on layer 1, such as requiring it to only contain AND gates, or only bounded fan-in gates.{{Pg|location=Section 11.10.3}}

The hierarchy for monotone $\backslash mathsf\{TC\}^0$

(that is, $\backslash mathsf\{TC\}^0$

without Boolean negations) is strongly separated. Specifically, for each $d$, there has been constructed a language that is decidable by a depth $d$ circuit family using only $O(n)$

AND and OR gates, but requires exponential size to compute by a monotone $\backslash mathsf\{TC\}^0\_\{d-1\}$

.{{Cite journal |last1=Håstad |first1=Johan |last2=Goldmann |first2=Mikael |date=June 1991 |title=On the power of small-depth threshold circuits |url=http://link.springer.com/10.1007/BF01272517 |journal=Computational Complexity |language=en |volume=1 |issue=2 |pages=113–129 |doi=10.1007/BF01272517 |issn=1016-3328}}

If the polynomial bound on the number of gates is relaxed, then $\backslash mathsf\{TC\}^0\_3$

is quite powerful. Specifically, any language in $\backslash mathsf\{ACC\}^0$

can be decided by a circuit family in $\backslash mathsf\{TC\}^0\_3$

(using Majority gates), except that it uses a quasi-polynomial number of gates (instead of polynomial).{{Cite book |last=Allender |first=E. |chapter=A note on the power of threshold circuits |date=October 1989 |title=30th Annual Symposium on Foundations of Computer Science |chapter-url=https://ieeexplore.ieee.org/document/63538 |pages=580–584 |doi=10.1109/SFCS.1989.63538|isbn=0-8186-1982-1 }}{{cite conference

| last = Yao | first = Andrew Chi-Chih | author-link = Andrew Yao

| contribution = On ACC and threshold circuits

| doi = 10.1109/FSCS.1990.89583

| pages = 619–627

| publisher = IEEE Computer Society

| title = 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22–24, 1990, Volume II

| contribution-url = https://scholar.archive.org/work/qzvve2rlijhyvnsl7ql2zdtw4u

| year = 1990| isbn = 0-8186-2082-X }} This result is optimal, in that there exists a function that is computable with 3 layers of $\backslash mathsf\{AC\}^0$

, but requires at least an exponential number of gates for $\backslash mathsf\{TC\}^0\_2$

(using Majority gates).{{citation

| last = Sherstov | first = Alexander A.

| doi = 10.1137/08071421X

| issue = 6

| journal = SIAM Journal on Computing

| mr = 2491551

| pages = 2113–2129

| title = Separating {{math|AC⁰}} from depth-2 majority circuits

| volume = 38

| year = 2009}}

{{reflist}}

• {{cite book | last1=Clote | first1=Peter | last2=Kranakis |first2=Evangelos | title=Boolean functions and computation models | series=Texts in Theoretical Computer Science. An EATCS Series | location=Berlin | publisher=Springer-Verlag | year=2002 | isbn=3-540-59436-1 | zbl=1016.94046 }}
• {{Cite book |last1=Parberry |first1=Ian |url=https://direct.mit.edu/books/book/2708/Circuit-Complexity-and-Neural-Networks |title=Circuit Complexity and Neural Networks |last2=Garey |first2=Michael R. |last3=Meyer |first3=Albert |date=1994-07-27 |publisher=The MIT Press |isbn=978-0-262-28124-9 |language=en |doi=10.7551/mitpress/1836.001.0001}}

• {{CZoo|TC⁰|T#tc0}}

{{ComplexityClasses}}

Category:Circuit complexity

Category:Complexity classes