In theoretical computer science, and specifically computational complexity theory and circuit complexity, TC0 (Threshold Circuit) is the first class in the hierarchy of TC classes. TC0 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 gatess, or equivalently, threshold gates.

TC0 contains several important problems, such as sorting n n-bit numbers, multiplying two n-bit numbers, integer division or recognizing the Dyck language with multiple 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.

Definitions

A Boolean circuit family is in the TC0, such that

• .

• unbounded fan-in layers.

• .

Equivalently, instead of majority gates, we can use threshold gates. A threshold gate is also called an artificial neuron.

. Therefore, TC0 such that

• .

• .

• .

.

In arithmetic circuit complexity theory.

Complexity class relations

We can relate TC0 to other circuit classes, including AC0 and NC1 as follows: is a strict inclusion is "one of the main open problems in circuit complexity". is a strict inclusion! This is in some sense unsurprising, since there is no natural proof, assuming that there is a cryptographically secure pseudorandom number generator, which have been explicitly constructed under the assumption that factoring Blum integers), which is widely suspected to be true. More generally, randomness and hardness for have been shown to be closely related. was only proven in 2011.

are incomparable as well.

Note that, while the nondeterministic time hierarchy theorem, both complexity classes are uniform, meaning that a single Turing machine possible inputs to verify that the circuit is correct.

.

Uniform TC0

DLOGTIME, because it is equivalent to first-order logic with Majority quantifiers.., neither too strong nor too weak. Specifically, because P.

The permanent.

.

The functional version of the uniform TC0. over non-negative integers that are bounded by functions of FP is in the uniform TC0.

Fine structure

TC0The 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:

• 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.

.

gates.

Arbitrary threshold gate

variables can be realized using integer weights of absolute value. It is known thatSee for a literature review.

denotes the class where the weight and thresholds are unbounded ("large weight threshold circuit"). This formalizes neural networks with real-valued activation functions.

.

Allowing the sigmoid activation function, assuming the weights are polynomially bounded.

Probabilistic version

Like how the P class has a probabilistic version BPP. It is defined as the class of languages that can be polynomial-probabilistically decided.

possibilities.

.

Similarly, (feedforward) Boltzmann machines, make the wrong output.

circuit.

Hierarchy

, 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., since it gives no algorithm for discovering the advice other than brute-force enumeration.

.

be defined as the parity function, or the XOR function. Then the following two separations are theorems:

• .

• , where

in a precise sense:

• gates.

• .

• .

.. 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.

The hierarchy for monotone.

(using Majority gates), except that it uses a quasi-polynomial number of gates (instead of polynomial). (using Majority gates).

References

Further reading

External links