TC0

From Wikipedia, the free encyclopedia

The correct title of this article is TC0 . It features superscript or subscript characters that are substituted or omitted because of technical limitations.

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

TC0 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.

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

[edit] 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).

[edit] 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; Heribert Vollmer (1999). "Lindström Quantifiers and Leaf Language Definability" (pdf). Electronic Colloquium on Computational Complexity (TR96-005).