Intheoretical computer science, and specificallycomputational complexity theory andcircuit complexity,TC (Threshold Circuit) is acomplexity class ofdecision problems that can be recognized by threshold circuits, which areBoolean circuits withAND,OR, andMajority gates, or equivalently,threshold gates. For each fixedi, the complexity classTCⁱ consists of all languages that can be recognized by a family of threshold circuits of depth${\displaystyle O({\log }^{i}n)}$,polynomial size, and unboundedfan-in. The classTC is defined via

${\displaystyle \text{TC}=\bigcup _{i\ge 0}{\text{TC}}^i.}$

The class was proposed in 1988 to formalize the computational complexity ofartificial neural networks.^[1]

The relationship between the TC,NC and theAC hierarchy can be summarized as follows:

${\displaystyle {\text{NC}}^i\subseteq {\text{AC}}^i\subseteq {\text{TC}}^i\subseteq {\text{NC}}^{i+1}.}$

In particular, we know that

${\displaystyle {\text{NC}}^0⊊{\text{AC}}^0⊊{\text{TC}}^0\subseteq {\text{NC}}^1.}$

The first strict containment follows from the fact thatNC⁰ cannot compute any function that depends on all the input bits. Thus choosing a problem that is trivially inAC⁰ and depends on all bits separates the two classes. (For example, consider the OR function.) The strict containmentAC⁰ ⊊TC⁰ follows because parity and majority (which are both inTC⁰) were shown to be not inAC⁰.^[2][3]

As an immediate consequence of the above containments, we have that NC = AC = TC.

• Vollmer, Heribert (1999).Introduction to Circuit Complexity. Berlin: Springer.ISBN 3-540-64310-9.

• Circuit complexity
• Complexity classes