- TC0
TC0 is a
complexity class used incircuit complexity . It is the first class in the hierarchy of TC classes.TC0 contains all languages which are decided by
boolean circuit s with constant depth and polynomial size, cointaining only unbounded-faninAND gate s,OR gate s, andmajority gate s. Equivalently,threshold gate s can be used instead of majority gates.TC0 contains several important problems, such as sorting "n" "n"-bit numbers, and multiplying two "n"-bit numbers.
Complexity class relations
We can relate TC0 to other circuit classes, including AC0 and NC1; 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
Wikimedia Foundation. 2010.