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:

\mathsf^0 \subsetneq \mathsf^0 \subsetneq \mathsf^0 \subseteq \mathsf^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 $\mathsf^0 \subsetneq \mathsf$. (Allender 1996, as cited in Burtschick 1999).

Basis for uniform $\mbox^0$

The functional version of the uniform $\mbox^0$ coincides with the closure with respect to composition of the projections and one of the following function sets $\$, $\$. 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,\ldots,x_n)$ over non-negative integers that are bounded by functions of FP and $(y\textf(x_1,\ldots,x_n))$ is in the uniform $\mbox^0$.

References

*
*
*
*

External links

*

{{ComplexityClasses

Circuit complexity
Complexity classes