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}$ .^[1]

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.

^ M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory, 17:13–27, 1984.