TC (complexity)

In circuit complexity, TC is a complexity class hierarchy. Each class, TCⁱ, consists of the languages recognized by Boolean circuits with depth $O(\log ^{i}n)$ and a polynomial number of unlimited-fanin AND, OR gates and Majority gates.

Relation to NC and AC

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

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

The strict containment ${AC}^{i}\subsetneq {TC}^{i}$ follows because parity (which is in ${TC}^{0}$) was shown to be not in ${AC}^{0}$.

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

References

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