TC0

A Boolean circuit family is a sequence of Boolean circuits C_1, C_2, C_3, \dots consisting of a feedforward network of Boolean functions. A binary language L \in 2^* is in the TC0 class if there exists a Boolean circuit family C_1, C_2, C_3, \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 \in 2^n , we have x \in L iff 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 inputs is defined by a list of weights w_1, \dots, w_k and a single threshold \theta. Upon binary inputs x_1, \dots, x_k, it outputs +1 if \sum_i w_i x_k > \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: \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], and thresholds bounded within [-M, +M]. Therefore, TC0 can be defined equivalently as the languages decidable by some Boolean circuit family C_1, C_2, C_3, \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 \pm p(n). • For each x \in 2^n , we have x \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 \mathsf{TC}^0. In arithmetic circuit complexity theory, \mathsf{TC}^0 can be equivalently characterized as the class of languages defined as the images of \mathrm{sign} \circ f_n, where each f_n : \{0, 1 \}^n \to \Z is computed by a polynomial-size constant-depth unbounded-fan-in arithmetic circuits with + and × gates, and constants from \{-1, 0, +1\}. ==Complexity class relations==

{{unsolved|computer science|\mathsf{TC}^0 \overset{?}{=} \mathsf{NC}^1}} We can relate TC0 to other circuit classes, including AC0 and NC1 as follows: \mathsf{AC}^0 \subsetneq \mathsf{AC}^0[p] \subsetneq \mathsf{TC}^0 \subseteq \mathsf{NC}^1. Whether \mathsf{TC}^0 \subseteq \mathsf{NC}^1 is a strict inclusion is "one of the main open problems in circuit complexity". More generally, randomness and hardness for have been shown to be closely related. It is also an open question whether \mathsf{NEXP} \subseteq \mathsf{TC}^0 . Indeed, \mathsf{NEXP} \not\subseteq \mathsf{ACC}^0 was only proven in 2011. Note that because non-uniform \mathsf{TC}^0 and \mathsf{ACC}^0 can compute functions that are not Turing-computable, it is certainly the case that \mathsf{TC}^0 \not\subseteq \mathsf{NEXP} and \mathsf{ACC}^0 \not\subseteq \mathsf{NEXP} . The 2011 result simply shows that \mathsf{ACC}^0 and \mathsf{NEXP} are incomparable classes. The open question is whether \mathsf{TC}^0 and \mathsf{NEXP} are incomparable as well. Note that, while the nondeterministic time hierarchy theorem proves that \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 \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^{\mathsf{poly}(n)} possible Boolean circuits of bounded depth and \mathsf{poly}(n) size, then checking all 2^n possible inputs to verify that the circuit is correct. It has been proven that if \mathsf{TC}^0 = \mathsf{NC}^1, then any \epsilon > 0, there exists a \mathsf{TC}^0 circuit family of gate number O(n^{1+\epsilon}) that solves the Boolean Formula Evaluation problem. Thus, any superlinear bound suffices to prove \mathsf{TC}^0 \neq \mathsf{NC}^1. ==Uniform TC0==

DLOGTIME-uniform \mathsf{TC}^0 is also known as \mathsf{FOM} , because it is equivalent to first-order logic with Majority quantifiers. Specifically, given a logic formula that takes x_1, x_2, \dots, x_n Boolean variables, a Majority quantifier M is used as follows: given a formula with exactly one free variable \phi(x), the quantified Mx \phi(x) is true iff \phi(x_i) is true for over half of i \in 1:n, Integer division (given x, y n-bit integers, find \lfloor x/y\rfloor), powering (given x an n-bit integer, and k a O(\ln(n))-bit integer, find x^k), and iterated multiplication (multiplying n of n-bit integers) are all in DLOGTIME-uniform \mathsf{TC}^0 . The permanent of a 0-1 matrix is not in uniform \mathsf{TC}^0 . Uniform \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 \,\stackrel{.}{-}\, m, n\wedge m, \lfloor n/m \rfloor, 2^{\lfloor \log_2 n \rfloor^2} \}, \{n+m, n \,\stackrel{.}{-}\, m, n\wedge m, \lfloor n/m \rfloor, n^{\lfloor \log_2 m \rfloor} \}. Here n \,\stackrel{.}{-}\, m=\max(0,n-m), n\wedge m is a bitwise AND of n and m. By functional version one means the set of all functions f(x_1,\ldots,x_n) over non-negative integers that are bounded by functions of FP and (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 \mathsf{TC}^0_d be the class of languages decidable by a threshold circuit family of up to depth d:\mathsf{TC}^0_1 \subset \mathsf{TC}^0_2 \subset \cdots \subset \mathsf{TC}^0 = \bigcup_{d=1}^\infty \mathsf{TC}^0_d 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 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 \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. 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 \mathsf{poly}(n) gates.\frac 12 n \log n - 2n + o(n) \leq \log_2 W(n) \leq \frac 12 n \log n - n + o(n)See for a literature review. Sometimes the class of polynomial-bounded weights and thresholds with depth d is denoted as \widehat{\mathsf{LT}}_d := \mathsf{TC}_d^0, and \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 threshold circuit can be simulated uniformly by a polynomial-size majority circuit of depth d+1. Therefore, \mathsf{TC}_d^0 \subset \mathsf{LT}_d \subset \mathsf{TC}_{d+1}^0. It has been proven that \mathsf{TC}_2^0 \subsetneq \mathsf{LT}_2. Probabilistic version Like how the P class has a probabilistic version BPP, the \mathsf{TC}^0 has a probabilistic version \mathsf{RTC}^0. It is defined as the class of languages that can be polynomial-probabilistically decided. Sometimes, this class is also called \mathsf{BPTC}^0, in a closer analogy with BPP. In this definition, the probability that C_n(x, y) = +1 is at least \frac 23, and if x \not\in L, then the probability that C_n(x, y) = +1 is at most \frac 13. By the standard trick of sampling many times then taking the majority opinion, any d-layer \mathsf{RTC}^0 circuit can be converted to a (d+1)-layer \mathsf{BPTC}^0 circuit. Hierarchy Analogous to how \mathsf{TC}^0_1 \subset \mathsf{TC}^0_2 \subset \cdots \subset \mathsf{TC}^0 = \bigcup_{d=1}^\infty \mathsf{TC}^0_d , \mathsf{RTC}^0 can also be divided into\mathsf{RTC}^0_1 \subset \mathsf{RTC}^0_2 \subset \cdots \subset \mathsf{RTC}^0 = \bigcup_{d=1}^\infty \mathsf{RTC}^0_dBy definition, \mathsf{TC}^0_d \subset \mathsf{RTC}^0_d. Furthermore, since \mathsf{RTC}^0_d \subset \mathsf{TC}^0_{d+1} , Let \oplus be defined as the parity function, or the XOR function. Then the following two separations are theorems: • If the weights of the bottom gates of a threshold circuit of depth 2 computing \mathrm{IP}_n do not exceed 2^{n / 3}, then the top gate must have fanin at least 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, \mathsf{TC}^0 = \mathsf{TC}^0_{3}. If the polynomial bound on the number of gates is relaxed, then \mathsf{TC}^0_3 is quite powerful. Specifically, any language in \mathsf{ACC}^0 can be decided by a circuit family in \mathsf{TC}^0_3 (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 \mathsf{AC}^0 , but requires at least an exponential number of gates for \mathsf{TC}^0_2 (using Majority gates). ==References==