In theoretical computer science, and specifically computational complexity theory and circuit complexity, **TC** is a complexity class of decision problems that can be recognized by threshold circuits, which are Boolean circuits with AND, OR, and Majority gates. For each fixed *i*, the complexity class **TC**^{i} consists of all languages that can be recognized by a family of threshold circuits of depth $O(\log ^{i}n)$, polynomial size, and unbounded fan-in. The class **TC** is defined via

- ${\mbox{TC))=\bigcup _{i\geq 0}{\mbox{TC))^{i}.$

##
Relation to NC and AC

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

- ${\mbox{NC))^{i}\subseteq {\mbox{AC))^{i}\subseteq {\mbox{TC))^{i}\subseteq {\mbox{NC))^{i+1}.$

In particular, we know that

- ${\mbox{NC))^{0}\subsetneq {\mbox{AC))^{0}\subsetneq {\mbox{TC))^{0}\subseteq {\mbox{NC))^{1}.$

The first strict containment follows from the fact that **NC**^{0} cannot compute any function that depends on all the input bits. Thus choosing a problem that is trivially in **AC**^{0} and depends on all bits separates the two classes. (For example, consider the OR function.) The strict containment **AC**^{0} ⊊ **TC**^{0} follows because parity and majority (which are both in **TC**^{0}) were shown to be not in **AC**^{0}.^{[1]}^{[2]}

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