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

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

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

In particular, we know that

${\displaystyle {\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.