title: TC (complexity)
text: # TC (complexity)
  
  In theoretical computer science, and specifically computational complexity theory and circuit complexity, TC is a complexity class of decision problems that can be recognized by threshold circuits, which are Boolean circuits with AND, OR, and Majority gates. For each fixed i, the complexity class $TC^i$ consists of all languages that can be recognized by a family of threshold circuits of depth $O(\log ^{i}n)$, polynomial size, and unbounded fan-in. The class TC is defined via
  
      ${\mbox{TC}}=\bigcup _{i\geq 0}{\mbox{TC}}^{i}.$
  
  ## Relation to NC and AC
  
  The relationship between the TC, NC and the AC hierarchy can be summarized as follows:
  
      ${\mbox{NC}}^{i}\subseteq {\mbox{AC}}^{i}\subseteq {\mbox{TC}}^{i}\subseteq {\mbox{NC}}^{i+1}.$
  
  In particular, we know that
  
      ${\mbox{NC}}^{0}\subsetneq {\mbox{AC}}^{0}\subsetneq {\mbox{TC}}^{0}\subseteq {\mbox{NC}}^{1}.$
  
  The first strict containment follows from the fact that $NC^0$ cannot compute any function that depends on all the input bits. Thus choosing a problem that is trivially in $AC^0$ and depends on all bits separates the two classes. (For example, consider the OR function.) The strict containment $AC^0$ ⊊ $TC^0$ follows because parity and majority (which are both in $TC^0)$ were shown to be not in $AC^0.$
  
  As an immediate consequence of the above containments, we have that NC = AC = TC.
  
  