• Images
• Videos
• Documents
• Books
• Articles

Definitions

A Boolean circuit family is a sequence of Boolean circuits C 1 , C 2 , C 3 , … {\displaystyle C_{1},C_{2},C_{3},\dots } consisting of a feedforward network of Boolean functions. A binary language L ∈ 2 ∗ {\displaystyle L\in 2^{*}} is in the TC0 class if there exists a Boolean circuit family C 1 , C 2 , C 3 , … {\displaystyle C_{1},C_{2},C_{3},\dots } , such that

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

Equivalently, instead of majority gates, we can use threshold gates with integer weights and thresholds, bounded by a polynomial. A threshold gate with k {\displaystyle k} inputs is defined by a list of weights w 1 , … , w k {\displaystyle w_{1},\dots ,w_{k}} and a single threshold θ {\displaystyle \theta } . Upon binary inputs x 1 , … , x k {\displaystyle x_{1},\dots ,x_{k}} , it outputs + 1 {\displaystyle +1} if ∑ i w i x k > θ {\displaystyle \sum _{i}w_{i}x_{k}>\theta } , else it outputs − 1 {\displaystyle -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 ] {\displaystyle [-M,+M]} , If we also provide the network with negations of binary inputs: ¬ x 1 , … , ¬ x k {\displaystyle \neg x_{1},\dots ,\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 ] {\displaystyle [0,+M]} , and thresholds bounded within [ − M , + M ] {\displaystyle [-M,+M]} . Therefore, TC0 can be defined equivalently as the languages decidable by some Boolean circuit family C 1 , C 2 , C 3 , … {\displaystyle C_{1},C_{2},C_{3},\dots } such that

• There exists a polynomial function p {\displaystyle p} , and a constant d {\displaystyle d} .
• Each C n {\displaystyle C_{n}} is composed of up to p ( n ) {\displaystyle p(n)} threshold gates in up to d {\displaystyle d} layers, whose weights are non-negative integers, thresholds are integers, and both weights and thresholds are bounded within ± p ( n ) {\displaystyle \pm p(n)} .
• For each x ∈ 2 n {\displaystyle x\in 2^{n}} , we have x ∈ L {\displaystyle x\in L} iff C n ( x ) = 1 {\displaystyle 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 T C 0 {\displaystyle {\mathsf {TC}}^{0}} .

In arithmetic circuit complexity theory, T C 0 {\displaystyle {\mathsf {TC}}^{0}} can be equivalently characterized as the class of languages defined as the images of s i g n ∘ f n {\displaystyle \mathrm {sign} \circ f_{n}} , where each f n : { 0 , 1 } n → Z {\displaystyle f_{n}:\{0,1\}^{n}\to \mathbb {Z} } is computed by a polynomial-size constant-depth unbounded-fan-in arithmetic circuits with + and × gates, and constants from { − 1 , 0 , + 1 } {\displaystyle \{-1,0,+1\}} .³

Complexity class relations

Unsolved problem in computer science T C 0 = ? N C 1 {\displaystyle {\mathsf {TC}}^{0}{\overset {?}{=}}{\mathsf {NC}}^{1}} More unsolved problems in computer science

We can relate TC0 to other circuit classes, including AC0 and NC1 as follows:⁴

A C 0 ⊊ A C 0 [ p ] ⊊ T C 0 ⊆ N C 1 . {\displaystyle {\mathsf {AC}}^{0}\subsetneq {\mathsf {AC}}^{0}[p]\subsetneq {\mathsf {TC}}^{0}\subseteq {\mathsf {NC}}^{1}.}

Whether T C 0 ⊆ N C 1 {\displaystyle {\mathsf {TC}}^{0}\subseteq {\mathsf {NC}}^{1}} is a strict inclusion is "one of the main open problems in circuit complexity".⁵ In fact, it is even open whether T C 0 ⊆ P / p o l y {\displaystyle {\mathsf {TC}}^{0}\subseteq {\mathsf {P/poly}}} is a strict inclusion! This is in some sense unsurprising, since there is no natural proof for T C 0 ⊊ P / p o l y {\displaystyle {\mathsf {TC}}^{0}\subsetneq {\mathsf {P/poly}}} , assuming that there is a cryptographically secure pseudorandom number generator in T C 0 {\displaystyle {\mathsf {TC}}^{0}} , which have been explicitly constructed under the assumption that factoring Blum integers is hard (i.e. requires circuits of size 2 p o l y ( n ) {\displaystyle 2^{{\mathsf {poly}}(n)}} ), which is widely suspected to be true.⁶ More generally, randomness and hardness for have been shown to be closely related.⁷ It is also an open question whether N E X P ⊆ T C 0 {\displaystyle {\mathsf {NEXP}}\subseteq {\mathsf {TC}}^{0}} . Indeed, N E X P ⊈ A C C 0 {\displaystyle {\mathsf {NEXP}}\not \subseteq {\mathsf {ACC}}^{0}} was only proven in 2011.⁸

Note that because non-uniform T C 0 {\displaystyle {\mathsf {TC}}^{0}} and A C C 0 {\displaystyle {\mathsf {ACC}}^{0}} can compute functions that are not Turing-computable, it is certainly the case that T C 0 ⊈ N E X P {\displaystyle {\mathsf {TC}}^{0}\not \subseteq {\mathsf {NEXP}}} and A C C 0 ⊈ N E X P {\displaystyle {\mathsf {ACC}}^{0}\not \subseteq {\mathsf {NEXP}}} . The 2011 result simply shows that A C C 0 {\displaystyle {\mathsf {ACC}}^{0}} and N E X P {\displaystyle {\mathsf {NEXP}}} are incomparable classes. The open question is whether T C 0 {\displaystyle {\mathsf {TC}}^{0}} and N E X P {\displaystyle {\mathsf {NEXP}}} are incomparable as well.

Note that, while the time hierarchy theorem proves that N P ⊊ N E X P {\displaystyle {\mathsf {NP}}\subsetneq {\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 T C 0 {\displaystyle {\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 p o l y ( n ) {\displaystyle 2^{{\mathsf {poly}}(n)}} possible Boolean circuits of bounded depth and p o l y ( n ) {\displaystyle {\mathsf {poly}}(n)} size, then checking all 2 n {\displaystyle 2^{n}} possible inputs to verify that the circuit is correct.

It has been proven that if T C 0 = N C 1 {\displaystyle {\mathsf {TC}}^{0}={\mathsf {NC}}^{1}} , then any ϵ > 0 {\displaystyle \epsilon >0} , there exists a T C 0 {\displaystyle {\mathsf {TC}}^{0}} circuit family of gate number O ( n 1 + ϵ ) {\displaystyle O(n^{1+\epsilon })} that solves the Boolean Formula Evaluation problem. Thus, any superlinear bound suffices to prove T C 0 ≠ N C 1 {\displaystyle {\mathsf {TC}}^{0}\neq {\mathsf {NC}}^{1}} .⁹

Uniform TC0

DLOGTIME-uniform T C 0 {\displaystyle {\mathsf {TC}}^{0}} is also known as F O M {\displaystyle {\mathsf {FOM}}} , because it is equivalent to first-order logic with Majority quantifiers.¹⁰ Specifically, given a logic formula that takes x 1 , x 2 , … , x n {\displaystyle x_{1},x_{2},\dots ,x_{n}} Boolean variables, a Majority quantifier M {\displaystyle M} is used as follows: given a formula with exactly one free variable ϕ ( x ) {\displaystyle \phi (x)} , the quantified M x ϕ ( x ) {\displaystyle Mx\phi (x)} is true iff ϕ ( x i ) {\displaystyle \phi (x_{i})} is true for over half of i ∈ 1 : n {\displaystyle i\in 1:n} , Integer division (given x , y {\displaystyle x,y} n {\displaystyle n} -bit integers, find ⌊ x / y ⌋ {\displaystyle \lfloor x/y\rfloor } ), powering (given x {\displaystyle x} an n {\displaystyle n} -bit integer, and k {\displaystyle k} a O ( ln ⁡ ( n ) ) {\displaystyle O(\ln(n))} -bit integer, find x k {\displaystyle x^{k}} ), and iterated multiplication (multiplying n {\displaystyle n} of n {\displaystyle n} -bit integers) are all in DLOGTIME-uniform T C 0 {\displaystyle {\mathsf {TC}}^{0}} .¹¹¹² It is usually considered the appropriate level of uniformity for T C 0 {\displaystyle {\mathsf {TC}}^{0}} , neither too strong nor too weak. Specifically, because P is usually suspected to be stronger than T C 0 {\displaystyle {\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 T C 0 {\displaystyle {\mathsf {TC}}^{0}} .¹³

The permanent of a 0-1 matrix is not in uniform T C 0 {\displaystyle {\mathsf {TC}}^{0}} .¹⁴

Uniform T C 0 ⊊ P P {\displaystyle {\mathsf {TC}}^{0}\subsetneq {\mathsf {PP}}} .¹⁵

The functional version of the uniform TC0 coincides with the closure with respect to composition of the projections and one of the following function sets { n + m , n − . m , n ∧ m , ⌊ n / m ⌋ , 2 ⌊ log 2 ⁡ n ⌋ 2 } {\displaystyle \{n+m,n\,{\stackrel {.}{-}}\,m,n\wedge m,\lfloor n/m\rfloor ,2^{\lfloor \log _{2}n\rfloor ^{2}}\}} , { n + m , n − . m , n ∧ m , ⌊ n / m ⌋ , n ⌊ log 2 ⁡ m ⌋ } {\displaystyle \{n+m,n\,{\stackrel {.}{-}}\,m,n\wedge m,\lfloor n/m\rfloor ,n^{\lfloor \log _{2}m\rfloor }\}} .¹⁶ Here n − . m = max ( 0 , n − m ) {\displaystyle n\,{\stackrel {.}{-}}\,m=\max(0,n-m)} , n ∧ m {\displaystyle n\wedge m} is a bitwise AND of n {\displaystyle n} and m {\displaystyle m} . By functional version one means the set of all functions f ( x 1 , … , x n ) {\displaystyle f(x_{1},\ldots ,x_{n})} over non-negative integers that are bounded by functions of FP and ( y -th bit of  f ( x 1 , … , x n ) ) {\displaystyle (y{\text{-th bit of }}f(x_{1},\ldots ,x_{n}))} is in the uniform TC0.

Fine structure

TC0 can be divided further, into a hierarchy of languages requiring up to 1 layer, 2 layers, etc. Let T C d 0 {\displaystyle {\mathsf {TC}}_{d}^{0}} be the class of languages decidable by a threshold circuit family of up to depth d {\displaystyle d} : T C 1 0 ⊂ T C 2 0 ⊂ ⋯ ⊂ T C 0 = ⋃ d = 1 ∞ T C d 0 {\displaystyle {\mathsf {TC}}_{1}^{0}\subset {\mathsf {TC}}_{2}^{0}\subset \cdots \subset {\mathsf {TC}}^{0}=\bigcup _{d=1}^{\infty }{\mathsf {TC}}_{d}^{0}} The hierarchy can be even more finely divided.

MAJ vs threshold

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 {\displaystyle 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 {\displaystyle n} -input threshold gate with arbitrary (unbounded) integer weights and thresholds, it constructs a depth-2 circuit using p o l y ( n ) {\displaystyle {\mathsf {poly}}(n)} -many AND, OR, NOT, and MAJ gates. Thus, any polynomial-size, depth- d {\displaystyle d} threshold circuit can be simulated uniformly by a polynomial-size majority circuit of depth d + 1 {\displaystyle d+1} .¹⁷¹⁸

As a separation theorem, it is known that the n {\displaystyle n} -input Boolean inner product function (IP), defined below, is computable by a majority circuit with 3 layers and O ( n ) {\displaystyle O(n)} gates, but is not computable by a threshold circuit with 2 layers and p o l y ( n ) {\displaystyle {\mathsf {poly}}(n)} gates.¹⁹: Section 11.10.2 

Arbitrary threshold gate

For any fixed n {\displaystyle 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 , … , w n , θ {\displaystyle w_{1},\dots ,w_{n},\theta } to be integers. Let W ( n ) {\displaystyle W(n)} be the smallest number W {\displaystyle W} such that every possible real threshold function of n {\displaystyle n} variables can be realized using integer weights of absolute value ≤ W {\displaystyle \leq W} . It is known that²⁰ 1 2 n log ⁡ n − 2 n + o ( n ) ≤ log 2 ⁡ W ( n ) ≤ 1 2 n log ⁡ n − n + o ( n ) {\displaystyle {\frac {1}{2}}n\log n-2n+o(n)\leq \log _{2}W(n)\leq {\frac {1}{2}}n\log n-n+o(n)} See ²¹: Section 11.10  for a literature review.

Sometimes the class of polynomial-bounded weights and thresholds with depth d {\displaystyle d} is denoted as L T ^ d := T C d 0 {\displaystyle {\widehat {\mathsf {LT}}}_{d}:={\mathsf {TC}}_{d}^{0}} , and L T d {\displaystyle {\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.²²

As previously stated, any polynomial-size, depth- d {\displaystyle d} threshold circuit can be simulated uniformly by a polynomial-size majority circuit of depth d + 1 {\displaystyle d+1} . Therefore, T C d 0 ⊂ L T d ⊂ T C d + 1 0 {\displaystyle {\mathsf {TC}}_{d}^{0}\subset {\mathsf {LT}}_{d}\subset {\mathsf {TC}}_{d+1}^{0}} . It has been proven that T C 2 0 ⊊ L T 2 {\displaystyle {\mathsf {TC}}_{2}^{0}\subsetneq {\mathsf {LT}}_{2}} .²³

Allowing the sigmoid activation function σ {\displaystyle \sigma } does not increase the power, that is, T C d 0 = T C d 0 ( σ ) {\displaystyle {\mathsf {TC}}_{d}^{0}={\mathsf {TC}}_{d}^{0}(\sigma )} for all d ≥ 1 {\displaystyle d\geq 1} , assuming the weights are polynomially bounded.²⁴

Probabilistic version

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

Let C 1 , C 2 , C 3 , … {\displaystyle C_{1},C_{2},C_{3},\dots } be a Boolean circuit family that takes two kinds of inputs. A given circuit C n {\displaystyle C_{n}} takes the deterministic inputs x 1 , … , x n {\displaystyle x_{1},\dots ,x_{n}} , and the random inputs y 1 , … , y m {\displaystyle y_{1},\dots ,y_{m}} , where m = p o l y ( n ) {\displaystyle m={\mathsf {poly}}(n)} . The random inputs are sampled uniformly over all 2 m {\displaystyle 2^{m}} possibilities.

A language L ⊂ 2 ∗ {\displaystyle L\subset 2^{*}} is decided polynomial-probabilistically by the family if for each x ∈ 2 n {\displaystyle x\in 2^{n}} , if x ∈ L {\displaystyle x\in L} , then the probability that C n ( x , y ) = + 1 {\displaystyle C_{n}(x,y)=+1} is at least 1 2 + 1 p o l y ( n ) {\displaystyle {\frac {1}{2}}+{\frac {1}{{\mathsf {poly}}(n)}}} , and if x ∉ L {\displaystyle x\not \in L} , then the probability that C n ( x , y ) = + 1 {\displaystyle C_{n}(x,y)=+1} is at most 1 2 − 1 p o l y ( n ) {\displaystyle {\frac {1}{2}}-{\frac {1}{{\mathsf {poly}}(n)}}} .

Similarly, (feedforward) Boltzmann machines have been modelled as R T C 0 {\displaystyle {\mathsf {RTC}}^{0}} circuits with boundedly-unreliable threshold units. That is, each threshold unit may, independently at random, with a bounded probability ϵ < 1 / 2 {\displaystyle \epsilon <1/2} , make the wrong output.²⁶

Sometimes, this class is also called B P T C 0 {\displaystyle {\mathsf {BPTC}}^{0}} , in a closer analogy with BPP. In this definition, the probability that C n ( x , y ) = + 1 {\displaystyle C_{n}(x,y)=+1} is at least 2 3 {\displaystyle {\frac {2}{3}}} , and if x ∉ L {\displaystyle x\not \in L} , then the probability that C n ( x , y ) = + 1 {\displaystyle C_{n}(x,y)=+1} is at most 1 3 {\displaystyle {\frac {1}{3}}} . By the standard trick of sampling many times then taking the majority opinion, any d {\displaystyle d} -layer R T C 0 {\displaystyle {\mathsf {RTC}}^{0}} circuit can be converted to a ( d + 1 ) {\displaystyle (d+1)} -layer B P T C 0 {\displaystyle {\mathsf {BPTC}}^{0}} circuit.

Hierarchy

Analogous to how T C 1 0 ⊂ T C 2 0 ⊂ ⋯ ⊂ T C 0 = ⋃ d = 1 ∞ T C d 0 {\textstyle {\mathsf {TC}}_{1}^{0}\subset {\mathsf {TC}}_{2}^{0}\subset \cdots \subset {\mathsf {TC}}^{0}=\bigcup _{d=1}^{\infty }{\mathsf {TC}}_{d}^{0}} , R T C 0 {\displaystyle {\mathsf {RTC}}^{0}} can also be divided into R T C 1 0 ⊂ R T C 2 0 ⊂ ⋯ ⊂ R T C 0 = ⋃ d = 1 ∞ R T C d 0 {\displaystyle {\mathsf {RTC}}_{1}^{0}\subset {\mathsf {RTC}}_{2}^{0}\subset \cdots \subset {\mathsf {RTC}}^{0}=\bigcup _{d=1}^{\infty }{\mathsf {RTC}}_{d}^{0}} By definition, T C d 0 ⊂ R T C d 0 {\displaystyle {\mathsf {TC}}_{d}^{0}\subset {\mathsf {RTC}}_{d}^{0}} . Furthermore, since R T C d 0 ⊂ T C d + 1 0 {\displaystyle {\mathsf {RTC}}_{d}^{0}\subset {\mathsf {TC}}_{d+1}^{0}} ,²⁷ there is a full hierarchy: T C 1 0 ⊂ R T C 1 0 ⊂ T C 2 0 ⊂ R C 2 0 ⊂ ⋯ ⊂ T C 0 = R T C 0 {\displaystyle {\mathsf {TC}}_{1}^{0}\subset {\mathsf {RTC}}_{1}^{0}\subset {\mathsf {TC}}_{2}^{0}\subset {\mathsf {RC}}_{2}^{0}\subset \cdots \subset {\mathsf {TC}}^{0}={\mathsf {RTC}}^{0}} Similarly, allowing boundedly-unreliable threshold units, a R T C d 0 {\displaystyle {\mathsf {RTC}}_{d}^{0}} circuit can be converted to a T C d + 1 0 {\displaystyle {\mathsf {TC}}_{d+1}^{0}} 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 T C 0 {\displaystyle {\mathsf {TC}}^{0}} , since it gives no algorithm for discovering the advice other than brute-force enumeration.

Similarly, R T C 0 / p o l y = T C 0 / p o l y {\displaystyle {\mathsf {RTC}}^{0}/{\mathsf {poly}}={\mathsf {TC}}^{0}/{\mathsf {poly}}} .²⁹

Let ⊕ {\displaystyle \oplus } be defined as the parity function, or the XOR function. Then the following two separations are theorems:³⁰

• R T C 1 0 ⊊ T C 2 0 {\displaystyle {\mathsf {RTC}}_{1}^{0}\subsetneq {\mathsf {TC}}_{2}^{0}} : The PARITY function ⊕ {\displaystyle \oplus } is in T C 2 0 {\displaystyle {\mathsf {TC}}_{2}^{0}} , but not in R T C 1 0 {\displaystyle {\mathsf {RTC}}_{1}^{0}} .³¹
• T C 2 0 ⊊ R T C 2 0 {\displaystyle {\mathsf {TC}}_{2}^{0}\subsetneq {\mathsf {RTC}}_{2}^{0}} : The Boolean inner product function (IP) is in R T C 2 0 {\displaystyle {\mathsf {RTC}}_{2}^{0}} but not in T C 2 0 {\displaystyle {\mathsf {TC}}_{2}^{0}} , where³² I P n ( x 1 , … , x n , x 1 ′ , … , x n ′ ) = ⨁ i = 1 n A N D ( x i , x i ′ ) {\displaystyle \mathrm {IP} _{n}\left(x_{1},\ldots ,x_{n},x_{1}^{\prime },\ldots ,x_{n}^{\prime }\right)=\bigoplus _{i=1}^{n}\mathrm {AND} \left(x_{i},x_{i}^{\prime }\right)}

The inner product function falls outside T C 2 0 {\displaystyle {\mathsf {TC}}_{2}^{0}} in a precise sense:³³: Section 11.10.2 

• If the weights of the bottom gates of a threshold circuit of depth 2 computing I P n {\displaystyle \mathrm {IP} _{n}} are polynomial, then for any ϵ > 0 {\displaystyle \epsilon >0} , for all large enough n {\displaystyle n} , I P n {\displaystyle \mathrm {IP} _{n}} requires ≥ 2 ( 1 / 2 − ϵ ) n {\displaystyle \geq 2^{(1/2-\epsilon )n}} gates.³⁴
• If the weights of the top gate in a threshold circuit of depth 2 computing I P n {\displaystyle \mathrm {IP} _{n}} are at most 2 o ( n 1 / 3 ) {\displaystyle 2^{o\left(n^{1/3}\right)}} , then the top gate must have fanin at least 2 Ω ( n 1 / 3 ) {\displaystyle 2^{\Omega \left(n^{1/3}\right)}} .³⁵
• If the weights of the bottom gates of a threshold circuit of depth 2 computing I P n {\displaystyle \mathrm {IP} _{n}} do not exceed 2 n / 3 {\displaystyle 2^{n/3}} , then the top gate must have fanin at least 2 Ω ( n ) {\displaystyle 2^{\Omega (n)}} .³⁶

It is an open question how many levels the hierarchy has. It is also an open question whether the hierarchy collapses, that is, T C 0 = T C 3 0 {\displaystyle {\mathsf {TC}}^{0}={\mathsf {TC}}_{3}^{0}} .³⁷ In fact, there is still no exponential lower bound for L T 2 0 {\displaystyle {\mathsf {LT}}_{2}^{0}} . 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.³⁸: Section 11.10.3 

The hierarchy for monotone T C 0 {\displaystyle {\mathsf {TC}}^{0}} (that is, T C 0 {\displaystyle {\mathsf {TC}}^{0}} without Boolean negations) is strongly separated. Specifically, for each d {\displaystyle d} , there has been constructed a language that is decidable by a depth d {\displaystyle d} circuit family using only O ( n ) {\displaystyle O(n)} AND and OR gates, but requires exponential size to compute by a monotone T C d − 1 0 {\displaystyle {\mathsf {TC}}_{d-1}^{0}} .³⁹

If the polynomial bound on the number of gates is relaxed, then T C 3 0 {\displaystyle {\mathsf {TC}}_{3}^{0}} is quite powerful. Specifically, any language in A C C 0 {\displaystyle {\mathsf {ACC}}^{0}} can be decided by a circuit family in T C 3 0 {\displaystyle {\mathsf {TC}}_{3}^{0}} (using Majority gates), except that it uses a quasi-polynomial number of gates (instead of polynomial).⁴⁰⁴¹ This result is optimal, in that there exists a function that is computable with 3 layers of A C 0 {\displaystyle {\mathsf {AC}}^{0}} , but requires at least an exponential number of gates for T C 2 0 {\displaystyle {\mathsf {TC}}_{2}^{0}} (using Majority gates).⁴²

Further reading

• Clote, Peter; Kranakis, Evangelos (2002). Boolean functions and computation models. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. ISBN 3-540-59436-1. Zbl 1016.94046.
• Parberry, Ian; Garey, Michael R.; Meyer, Albert (1994-07-27). Circuit Complexity and Neural Networks. The MIT Press. doi:10.7551/mitpress/1836.001.0001. ISBN 978-0-262-28124-9.

External links

• Complexity Zoo: TC0

References

1. Hesse, William; Allender, Eric; Mix Barrington, David (2002). "Uniform constant-depth threshold circuits for division and iterated multiplication". Journal of Computer and System Sciences. 65 (4): 695–716. doi:10.1016/S0022-0000(02)00025-9. https://doi.org/10.1016%2FS0022-0000%2802%2900025-9 ↩

2. Parberry, Ian; Schnitger, Georg (1988-06-01). "Parallel computation with threshold functions". Journal of Computer and System Sciences. 36 (3): 278–302. doi:10.1016/0022-0000(88)90030-X. ISSN 0022-0000. https://dx.doi.org/10.1016/0022-0000%2888%2990030-X ↩

3. Agrawal, Manindra; Allender, Eric; Datta, Samir (April 2000). "On TC0, AC0, and Arithmetic Circuits". Journal of Computer and System Sciences. 60 (2): 395–421. doi:10.1006/jcss.1999.1675. https://linkinghub.elsevier.com/retrieve/pii/S0022000099916756 ↩

4. Vollmer, Heribert (1998). Introduction to circuit complexity. A uniform approach. Texts in Theoretical Computer Science. Berlin: Springer-Verlag. p. 126. ISBN 3-540-64310-9. Zbl 0931.68055. 3-540-64310-9 ↩

5. Vollmer, Heribert (1998). Introduction to circuit complexity. A uniform approach. Texts in Theoretical Computer Science. Berlin: Springer-Verlag. p. 126. ISBN 3-540-64310-9. Zbl 0931.68055. 3-540-64310-9 ↩

6. Naor, Moni; Reingold, Omer (March 2004). "Number-theoretic constructions of efficient pseudo-random functions". Journal of the ACM. 51 (2): 231–262. doi:10.1145/972639.972643. ISSN 0004-5411. https://dl.acm.org/doi/10.1145/972639.972643 ↩

7. Hatami, Pooya; Hoza, William M.; Tal, Avishay; Tell, Roei (February 2022). "Fooling Constant-Depth Threshold Circuits (Extended Abstract)". 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE. pp. 104–115. doi:10.1109/FOCS52979.2021.00019. ISBN 978-1-6654-2055-6. 978-1-6654-2055-6 ↩

8. Williams, Ryan (June 2011). "Non-uniform ACC Circuit Lower Bounds". 2011 IEEE 26th Annual Conference on Computational Complexity. pp. 115–125. doi:10.1109/CCC.2011.36. ISBN 978-1-4577-0179-5. 978-1-4577-0179-5 ↩

9. Allender, Eric; Koucký, Michal (March 2010). "Amplifying lower bounds by means of self-reducibility". Journal of the ACM. 57 (3): 1–36. doi:10.1145/1706591.1706594. ISSN 0004-5411. https://dl.acm.org/doi/10.1145/1706591.1706594 ↩

10. Mix Barrington, David A.; Immerman, Neil; Straubing, Howard (1990-12-01). "On uniformity within NC1". Journal of Computer and System Sciences. 41 (3): 274–306. doi:10.1016/0022-0000(90)90022-D. ISSN 0022-0000. https://dx.doi.org/10.1016/0022-0000%2890%2990022-D ↩

11. Hesse, William (2001), Orejas, Fernando; Spirakis, Paul G.; van Leeuwen, Jan (eds.), "Division Is In Uniform TC0", Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 2076, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 104–114, doi:10.1007/3-540-48224-5_9, ISBN 978-3-540-42287-7, retrieved 2025-03-19 978-3-540-42287-7 ↩

12. Hesse, William; Allender, Eric; Mix Barrington, David (2002). "Uniform constant-depth threshold circuits for division and iterated multiplication". Journal of Computer and System Sciences. 65 (4): 695–716. doi:10.1016/S0022-0000(02)00025-9. https://doi.org/10.1016%2FS0022-0000%2802%2900025-9 ↩

13. Santhanam, Rahul; Williams, Ryan (2014-06-01). "On Uniformity and Circuit Lower Bounds". Computational Complexity. 23 (2): 177–205. doi:10.1007/s00037-014-0087-y. hdl:20.500.11820/d254202f-5539-45ba-ba25-cfe680aa46e9. ISSN 1420-8954. https://link.springer.com/article/10.1007/s00037-014-0087-y ↩

14. Allender, Eric (1999). "The permanent requires large uniform threshold circuits". Chicago Journal of Theoretical Computer Science. 5 (1): 1–19. doi:10.4086/cjtcs.1999.007. ISSN 1073-0486. http://cjtcs.cs.uchicago.edu/articles/1999/7/contents.html ↩

15. Allender, E. (1996). "A note on uniform circuit lower bounds for the counting hierarchy". Proceedings 2nd International Computing and Combinatorics Conference (COCOON). Springer Lecture Notes in Computer Science. Vol. 1090. pp. 127–135. As cited in Burtschick, Hans-Jörg; Vollmer, Heribert (1998). "Lindström quantifiers and leaf language definability". International Journal of Foundations of Computer Science. 9 (3): 277–294. doi:10.1142/S0129054198000180. ECCC TR96-005. /wiki/Lecture_Notes_in_Computer_Science ↩

16. Volkov, Sergey. (2016). "Finite Bases with Respect to the Superposition in Classes of Elementary Recursive Functions, dissertation". arXiv:1611.04843 [cs.CC]. /wiki/ArXiv_(identifier) ↩

17. Goldmann, Mikael; Håstad, Johan; Razborov, Alexander (1992-12-01). "Majority gates vs. general weighted threshold gates". Computational Complexity. 2 (4): 277–300. doi:10.1007/BF01200426. ISSN 1420-8954. https://link.springer.com/article/10.1007/BF01200426 ↩

18. Goldmann, Mikael; Karpinski, Marek (February 1998). "Simulating Threshold Circuits by Majority Circuits". SIAM Journal on Computing. 27 (1): 230–246. doi:10.1137/S0097539794274519. ISSN 0097-5397. http://epubs.siam.org/doi/10.1137/S0097539794274519 ↩

19. Jukna, Stasys (2012). Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 978-3-642-24507-7. 978-3-642-24507-7 ↩

20. Alon, Noga; Vũ, Văn H (1997-07-01). "Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs". Journal of Combinatorial Theory, Series A. 79 (1): 133–160. doi:10.1006/jcta.1997.2780. ISSN 0097-3165. https://linkinghub.elsevier.com/retrieve/pii/S0097316597927801 ↩

21. Jukna, Stasys (2012). Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 978-3-642-24507-7. 978-3-642-24507-7 ↩

22. Šíma, Jiří; Orponen, Pekka (2003-12-01). "General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results". Neural Computation. 15 (12): 2727–2778. doi:10.1162/089976603322518731. ISSN 0899-7667. PMID 14629867. https://direct.mit.edu/neco/article/15/12/2727-2778/6791 ↩

23. Goldmann, Mikael; Håstad, Johan; Razborov, Alexander (1992-12-01). "Majority gates vs. general weighted threshold gates". Computational Complexity. 2 (4): 277–300. doi:10.1007/BF01200426. ISSN 1420-8954. https://link.springer.com/article/10.1007/BF01200426 ↩

24. Maass, W.; Schnitger, G.; Sontag, E.D. (1991). "On the computational power of sigmoid versus Boolean threshold circuits". [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science. IEEE Comput. Soc. Press. pp. 767–776. doi:10.1109/SFCS.1991.185447. ISBN 978-0-8186-2445-2. 978-0-8186-2445-2 ↩

25. Hajnal, András; Maass, Wolfgang; Pudlák, Pavel; Szegedy, Márió; Turán, György (April 1993). "Threshold circuits of bounded depth". Journal of Computer and System Sciences. 46 (2): 129–154. doi:10.1016/0022-0000(93)90001-D. https://linkinghub.elsevier.com/retrieve/pii/002200009390001D ↩

26. Parberry, Ian; Schnitger, Georg (1989-01-01). "Relating Boltzmann machines to conventional models of computation". Neural Networks. 2 (1): 59–67. doi:10.1016/0893-6080(89)90015-4. ISSN 0893-6080. https://www.sciencedirect.com/science/article/abs/pii/0893608089900154 ↩

27. Hajnal, András; Maass, Wolfgang; Pudlák, Pavel; Szegedy, Márió; Turán, György (April 1993). "Threshold circuits of bounded depth". Journal of Computer and System Sciences. 46 (2): 129–154. doi:10.1016/0022-0000(93)90001-D. https://linkinghub.elsevier.com/retrieve/pii/002200009390001D ↩

28. Parberry, Ian; Schnitger, Georg (1989-01-01). "Relating Boltzmann machines to conventional models of computation". Neural Networks. 2 (1): 59–67. doi:10.1016/0893-6080(89)90015-4. ISSN 0893-6080. https://www.sciencedirect.com/science/article/abs/pii/0893608089900154 ↩

29. Ajtai, Miklos; Ben-Or, Michael (1984). "A theorem on probabilistic constant depth Computations". Proceedings of the sixteenth annual ACM symposium on Theory of computing - STOC '84. ACM Press. pp. 471–474. doi:10.1145/800057.808715. ISBN 978-0-89791-133-7. 978-0-89791-133-7 ↩

30. Hajnal, András; Maass, Wolfgang; Pudlák, Pavel; Szegedy, Márió; Turán, György (April 1993). "Threshold circuits of bounded depth". Journal of Computer and System Sciences. 46 (2): 129–154. doi:10.1016/0022-0000(93)90001-D. https://linkinghub.elsevier.com/retrieve/pii/002200009390001D ↩

31. Hajnal, András; Maass, Wolfgang; Pudlák, Pavel; Szegedy, Márió; Turán, György (April 1993). "Threshold circuits of bounded depth". Journal of Computer and System Sciences. 46 (2): 129–154. doi:10.1016/0022-0000(93)90001-D. https://linkinghub.elsevier.com/retrieve/pii/002200009390001D ↩

32. Hajnal, András; Maass, Wolfgang; Pudlák, Pavel; Szegedy, Márió; Turán, György (April 1993). "Threshold circuits of bounded depth". Journal of Computer and System Sciences. 46 (2): 129–154. doi:10.1016/0022-0000(93)90001-D. https://linkinghub.elsevier.com/retrieve/pii/002200009390001D ↩

33. Jukna, Stasys (2012). Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 978-3-642-24507-7. 978-3-642-24507-7 ↩

34. Hajnal, András; Maass, Wolfgang; Pudlák, Pavel; Szegedy, Márió; Turán, György (April 1993). "Threshold circuits of bounded depth". Journal of Computer and System Sciences. 46 (2): 129–154. doi:10.1016/0022-0000(93)90001-D. https://linkinghub.elsevier.com/retrieve/pii/002200009390001D ↩

35. Hajnal, András; Maass, Wolfgang; Pudlák, Pavel; Szegedy, Márió; Turán, György (April 1993). "Threshold circuits of bounded depth". Journal of Computer and System Sciences. 46 (2): 129–154. doi:10.1016/0022-0000(93)90001-D. https://linkinghub.elsevier.com/retrieve/pii/002200009390001D ↩

36. Forster, Jürgen; Krause, Matthias; Lokam, Satyanarayana V.; Mubarakzjanov, Rustam; Schmitt, Niels; Simon, Hans Ulrich (2001), Hariharan, Ramesh; Vinay, V.; Mukund, Madhavan (eds.), "Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity", FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science, vol. 2245, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 171–182, doi:10.1007/3-540-45294-x_15, ISBN 978-3-540-43002-5, retrieved 2025-03-19 978-3-540-43002-5 ↩

37. Šíma, Jiří; Orponen, Pekka (2003-12-01). "General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results". Neural Computation. 15 (12): 2727–2778. doi:10.1162/089976603322518731. ISSN 0899-7667. PMID 14629867. https://direct.mit.edu/neco/article/15/12/2727-2778/6791 ↩

38. Jukna, Stasys (2012). Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 978-3-642-24507-7. 978-3-642-24507-7 ↩

39. Håstad, Johan; Goldmann, Mikael (June 1991). "On the power of small-depth threshold circuits". Computational Complexity. 1 (2): 113–129. doi:10.1007/BF01272517. ISSN 1016-3328. http://link.springer.com/10.1007/BF01272517 ↩

40. Allender, E. (October 1989). "A note on the power of threshold circuits". 30th Annual Symposium on Foundations of Computer Science. pp. 580–584. doi:10.1109/SFCS.1989.63538. ISBN 0-8186-1982-1. 0-8186-1982-1 ↩

41. Yao, Andrew Chi-Chih (1990). "On ACC and threshold circuits". 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22–24, 1990, Volume II. IEEE Computer Society. pp. 619–627. doi:10.1109/FSCS.1990.89583. ISBN 0-8186-2082-X. 0-8186-2082-X ↩

42. Sherstov, Alexander A. (2009), "Separating AC0 from depth-2 majority circuits", SIAM Journal on Computing, 38 (6): 2113–2129, doi:10.1137/08071421X, MR 2491551 /wiki/SIAM_Journal_on_Computing ↩