TC0

MAJ vs threshold

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

In detail, there is an explicit algorithm, by which, given a single ${\displaystyle n}$-input threshold gate with arbitrary (unbounded) integer weights and thresholds, it constructs a depth-2 circuit using ${\displaystyle {\mathsf {poly}}(n)}$-many AND, OR, NOT, and MAJ gates. Thus, any polynomial-size, depth-${\displaystyle d}$ threshold circuit can be simulated uniformly by a polynomial-size majority circuit of depth ${\displaystyle d+1}$.^[7][8]

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

Arbitrary threshold gate

For any fixed ${\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 ${\displaystyle w_{1},\dots ,w_{n},\theta }$ to be integers. Let ${\displaystyle W(n)}$ be the smallest number ${\displaystyle W}$ such that every possible real threshold function of ${\displaystyle n}$ variables can be realized using integer weights of absolute value ${\displaystyle \leq W}$. It is known that^[10]$${\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 ^{[9]: Section 11.10} for a literature review.

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

As previously stated, any polynomial-size, depth-${\displaystyle d}$ threshold circuit can be simulated uniformly by a polynomial-size majority circuit of depth ${\displaystyle d+1}$. Therefore, ${\displaystyle {\mathsf {TC}}_{d}^{0}\subset {\mathsf {LT}}_{d}\subset {\mathsf {TC}}_{d+1}^{0}}$.

Allowing the sigmoid activation function ${\displaystyle \sigma }$ does not increase the power, that is, ${\displaystyle {\mathsf {TC}}_{d}^{0}={\mathsf {TC}}_{d}^{0}(\sigma )}$ for all ${\displaystyle d\geq 1}$, assuming the weights are polynomially bounded.^[12]

Probabilistic version

Like how the P class has a probabilistic version BPP, the ${\displaystyle {\mathsf {TC}}^{0}}$ has a probabilistic version ${\displaystyle {\mathsf {RTC}}^{0}}$, defined in (Hajnal et al. 1993). It is defined as the class of languages that can be polynomial-probabilistically decided.

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

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

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

Hierarchy

Analogous to how ${\textstyle {\mathsf {TC}}_{1}^{0}\subset {\mathsf {TC}}_{2}^{0}\subset \cdots \subset {\mathsf {TC}}^{0}=\bigcup _{d=1}^{\infty }{\mathsf {TC}}_{d}^{0}}$, ${\displaystyle {\mathsf {RTC}}^{0}}$ can also be divided into$${\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, ${\displaystyle {\mathsf {TC}}_{d}^{0}\subset {\mathsf {RTC}}_{d}^{0}}$. (Hajnal et al. 1993) showed that ${\displaystyle {\mathsf {RTC}}_{d}^{0}\subset {\mathsf {TC}}_{d+1}^{0}}$, thus giving a full hierarchy:$${\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, it is shown that allowing boundedly-unreliable threshold units, a ${\displaystyle {\mathsf {RTC}}_{d}^{0}}$ circuit can be converted to a ${\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, and then takes a Majority over their outputs.^[13]

(Hajnal et al. 1993) also proved two separation theorems. Let ${\displaystyle \oplus }$ be defined as the parity function, or the XOR function.

• ${\displaystyle {\mathsf {RTC}}_{1}^{0}\subsetneq {\mathsf {TC}}_{2}^{0}}$: The PARITY function ${\displaystyle \oplus }$ is in ${\displaystyle {\mathsf {TC}}_{2}^{0}}$, but not in ${\displaystyle {\mathsf {RTC}}_{1}^{0}}$.
• ${\displaystyle {\mathsf {TC}}_{2}^{0}\subsetneq {\mathsf {RTC}}_{2}^{0}}$: The Boolean inner product function (IP) is in ${\displaystyle {\mathsf {RTC}}_{2}^{0}}$ but not in ${\displaystyle {\mathsf {TC}}_{2}^{0}}$.$${\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 IP falls outside ${\displaystyle {\mathsf {TC}}_{2}^{0}}$ in a precise sense:^{[9]: Section 11.10.2}

• If the weights of the bottom gates of a threshold circuit of depth 2 computing ${\displaystyle \mathrm {IP} _{n}}$ are polynomial, then for any ${\displaystyle \epsilon >0}$, for all large enough ${\displaystyle n}$, ${\displaystyle \mathrm {IP} _{n}}$ requires ${\displaystyle \geq 2^{(1/2-\epsilon )n}}$ gates.^[14]
• If the weights of the top gate in a threshold circuit of depth 2 computing ${\displaystyle \mathrm {IP} _{n}}$ are at most ${\displaystyle 2^{o\left(n^{1/3}\right)}}$, then the top gate must have fanin at least ${\displaystyle 2^{\Omega \left(n^{1/3}\right)}}$.^[14]
• If the weights of the bottom gates of a threshold circuit of depth 2 computing ${\displaystyle \mathrm {IP} _{n}}$ do not exceed ${\displaystyle 2^{n/3}}$, then the top gate must have fanin at least ${\displaystyle 2^{\Omega (n)}}$.^[15]

If the polynomial bound on the number of gates is relaxed, then ${\displaystyle {\mathsf {TC}}_{3}^{0}}$ is quite powerful. Specifically, any language in ${\displaystyle {\mathsf {ACC}}^{0}}$ can be decided by a circuit family in ${\displaystyle {\mathsf {TC}}_{3}^{0}}$, except that it uses a quasi-polynomial number of gates (instead of polynomial).

It is an open question how many levels the hierarchy has. It is also an open question whether the hierarchy collapses, that is, ${\displaystyle {\mathsf {TC}}^{0}={\mathsf {TC}}_{3}^{0}}$.^[11] In fact, there is still no exponential lower bound for ${\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.^{[9]: Section 11.10.3}