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, containing only unbounded fan-in AND gates, OR gates, NOT 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, multiplying two n-bit numbers, integer division or recognizing the Dyck language with two types of parentheses.

Complexity class relations

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

${𝖠𝖢}^0⊊{𝖠𝖢}^0[p]⊊{𝖳𝖢}^0\subseteq {𝖭𝖢}^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 uniform ${𝖳𝖢}^0⊊𝖯𝖯$. (Allender 1996, as cited in Burtschick 1999).

Basis for uniform TC⁰

The functional version of the uniform ${\text{TC}}^0$ coincides with the closure with respect to composition of the projections and one of the following function sets $\{n+m,n\stackrel{.}{-}m,n\wedge m,\lfloor n/m\rfloor ,2^{\lfloor {\log }_{2}n{\rfloor }^2}\}$, $\{n+m,n\stackrel{.}{-}m,n\wedge m,\lfloor n/m\rfloor ,n^{\lfloor {\log }_{2}m\rfloor }\}$. Here $n\stackrel{.}{-}m=\max (0,n-m)$, $n\wedge m$ is a bitwise AND of $n$ and $m$. By functional version one means the set of all functions $f(x_1,\dots ,x_n)$ over non-negative integers that are bounded by functions of FP and $(y\text{-th bit of }f(x_1,\dots ,x_n))$ is in the uniform ${\text{TC}}^0$.

References

• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite journal

External links

• Template:CZoo