TC0

TC⁰ is a complexity class used in circuit complexity. It is the first class in the hierarchy of TC classes.

TC⁰ contains all languages which are decided by boolean circuits with constant depth and polynomial size, cointaining only unbounded-fanin AND gates, OR gates, and majority gates. Equivalently, threshold gates can be used instead of majority gates.

TC⁰ contains several important problems, such as sorting n n-bit numbers, and multiplying two n-bit numbers.

Complexity class relations

We can relate TC⁰ to other circuit classes, including AC⁰ and NC¹; Vollmer 1999 p. 126 states:

${\mbox{AC}}^{0}\subsetneq {\mbox{AC}}^{0}[p]\subsetneq {\mbox{TC}}^{0}\subseteq {\mbox{NC}}^{1}.$

Vollmer states that the question of whether the last inclusion above is strict is "one of the main open problems in circuit complexity" (ibid.).

We also have that ${\mbox{TC}}^{0}\subsetneq {\mbox{PP}}$. (Allender 1996, as cited in Burtschick 1999).

References

• E. Allender. A note on uniform circuit lower bounds for the counting hierarchy. In Proceedings 2nd International Computing and Combinatorics Conference (COCOON), volume 1090 of Springer Lecture Notes in Computer Science, pages 127-135, 1996.
• Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 3-540-64310-9.
• Burtschick, Hans-Jörg (1999). "Lindström Quantifiers and Leaf Language Definability" (pdf). Electronic Colloquium on Computational Complexity (TR96-005). Retrieved 2006-11-20. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)