TC (complexity)

In theoretical computer science, and specifically computational complexity theory and circuit complexity, TC is a complexity class, and TCⁱ is a hierarchy of complexity classes. 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. The class TC is defined as

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

$\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⁰ cannot compute any function that depends on all the input bits. Thus choosing a problem that is trivially in AC⁰ and depends on all bits separates the two classes. (For example, consider the OR function.) The strict containment AC⁰ ⊊ TC⁰ follows because parity and majority (which are both in TC⁰) were shown to be not in AC⁰.^[1][2]

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

References

1. M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory, 17:13–27, 1984.
2. Håstad, Johan (1989), "Almost Optimal Lower Bounds for Small Depth Circuits", in Micali, Silvio, Randomness and Computation (PDF), Advances in Computing Research 5, JAI Press, pp. 6–20, ISBN 0-89232-896-7

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