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-fanin 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:

$\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 uniform $\mbox{TC}^0 \subsetneq \mbox{PP}$. (Allender 1996, as cited in Burtschick 1999).

External links

• Complexity Zoo: TC⁰