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.
*cite book | last = Vollmer | first = Heribert | title = Introduction to Circuit Complexity | year = 1999 | publisher = Springer | location = Berlin | id = ISBN 3-540-64310-9
*cite journal | last = Burtschick | first = Hans-Jörg | coauthors = Heribert Vollmer | title = Lindström Quantifiers and Leaf Language Definability | journal = Electronic Colloquium on Computational Complexity | issue = TR96-005 | url = http://eccc.hpi-web.de/eccc-reports/1996/TR96-005/Paper.pdf | format = pdf | accessdate = 2006-11-20 | year = 1999