TC (complexity)
# TC (complexity)

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

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

