In theoretical computer science, and specifically computational complexity theory and circuit complexity, TC⁰ (Threshold Circuit) is the first class in the hierarchy of TC classes. TC⁰ contains all languages which are decided by Boolean circuits with constant depth and polynomial size, containing only unbounded fan-in AND gates, OR gates, NOT gates, and MAJ gates, or equivalently, threshold gates.

TC⁰ contains several important problems, such as sorting n n-bit numbers, multiplying two n-bit numbers, integer division or recognizing the Dyck language with two types of parentheses. It is commonly used to model the computational complexity of bounded-depth neural networks, and indeed, it was originally proposed for this purpose.

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

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

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 ${\displaystyle {\mathsf {TC}}^{0}}$.

In arithmetic circuit complexity theory, ${\displaystyle {\mathsf {TC}}^{0}}$ can be equivalently characterized as the class of languages defined as the images of ${\displaystyle \mathrm {sign} \circ f_{n}}$, where each ${\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 ${\displaystyle \{-1,0,+1\}}$.

We can relate TC⁰ to other circuit classes, including AC⁰ and NC¹ as follows: