View source for TC0

{{short description|Complexity class used in circuit complexity}}
{{DISPLAYTITLE:TC<sup>0</sup>}}
'''TC<sup>0</sup>''' is a [[complexity class]] used in [[circuit complexity]].  It is the first class in the hierarchy of [[TC (complexity)|TC]] classes.

TC<sup>0</sup> contains all languages which are decided by [[Boolean circuit]]s with constant depth and polynomial size, containing only unbounded fan-in [[AND gate]]s, [[OR gate]]s, [[NOT gate]]s, and [[majority gate]]s.  Equivalently, [[threshold gate]]s can be used instead of majority gates.

TC<sup>0</sup> contains several important problems, such as sorting ''n'' ''n''-bit numbers, multiplying two ''n''-bit numbers, integer division<ref>{{cite journal|first1=William|last1=Hesse|first2=Eric|last2=Allender|first3=David|last3=Mix Barrington|title=Uniform constant-depth threshold circuits for division and iterated multiplication|journal=Journal of Computer and System Sciences|volume=65|year=2002|issue=4 |pages=695–716|doi=10.1016/S0022-0000(02)00025-9|doi-access=free}}</ref> or recognizing the [[Dyck language]] with two types of parentheses.

==Complexity class relations==
We can relate TC<sup>0</sup> to other circuit classes, including [[AC0|AC<sup>0</sup>]] and [[NC1 (complexity)|NC<sup>1</sup>]]; Vollmer 1999 p.&nbsp;126 states:
<blockquote>
<math>\mathsf{AC}^0 \subsetneq \mathsf{AC}^0[p] \subsetneq \mathsf{TC}^0 \subseteq \mathsf{NC}^1. </math>
</blockquote>
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 uniform <math>\mathsf{TC}^0 \subsetneq \mathsf{PP}</math>. (Allender 1996, as cited in Burtschick 1999).

==Basis for uniform TC<sup>0</sup>==

The functional version of the uniform <math>\mbox{TC}^0</math> coincides with the closure with respect to composition of the projections and one of the following function sets <math>\{n+m, n \,\stackrel{.}{-}\, m, n\wedge m, \lfloor n/m \rfloor, 2^{\lfloor \log_2 n \rfloor^2} \}</math>, <math>\{n+m, n \,\stackrel{.}{-}\, m, n\wedge m, \lfloor n/m \rfloor, n^{\lfloor \log_2 m \rfloor} \}</math>.<ref>{{cite arXiv |last=Volkov |first=Sergey. |eprint=1611.04843 |title=Finite Bases with Respect to the Superposition in Classes of Elementary Recursive Functions, dissertation |year=2016 |class=cs.CC }}</ref> Here <math>n \,\stackrel{.}{-}\, m=\max(0,n-m)</math>, <math>n\wedge m</math> is a bitwise AND of <math>n</math> and <math>m</math>. By functional version one means the set of all functions <math>f(x_1,\ldots,x_n)</math> over non-negative integers that are bounded by functions of [[FP_(complexity)|FP]] and <math>(y\text{-th bit of }f(x_1,\ldots,x_n))</math> is in the uniform <math>\mbox{TC}^0</math>.

==References==
{{reflist}}
*{{cite book | first=E. | last=Allender | chapter= A note on uniform circuit lower bounds for the counting hierarchy | title=Proceedings 2nd International Computing and Combinatorics Conference (COCOON) | volume=1090 | series=Springer [[Lecture Notes in Computer Science]] | pages=127–135 | year=1996 }}
*{{cite book | last1=Clote | first1=Peter | last2=Kranakis |first2=Evangelos | title=Boolean functions and computation models | series=Texts in Theoretical Computer Science. An EATCS Series | location=Berlin | publisher=[[Springer-Verlag]] | year=2002 | isbn=3-540-59436-1 | zbl=1016.94046 }}
*{{cite book | last = Vollmer | first = Heribert | title = Introduction to Circuit Complexity. A uniform approach | series=Texts in Theoretical Computer Science | year = 1999 | publisher = [[Springer-Verlag]] | location = Berlin | isbn = 3-540-64310-9 | zbl=0931.68055 }}
*{{cite journal
 | last1 = Burtschick | first1 = Hans-Jörg
 | last2 = Vollmer | first2 = Heribert
 | doi = 10.1142/S0129054198000180
 | id = {{ECCC|1996|96|005}}
 | issue = 3
 | journal = International Journal of Foundations of Computer Science
 | pages = 277–294
 | title = Lindström quantifiers and leaf language definability
 | volume = 9
 | year = 1998}}

==External links==
*{{CZoo|TC<sup>0</sup>|T#tc0}}

{{ComplexityClasses}}

[[Category:Circuit complexity]]
[[Category:Complexity classes]]