TC (complexité)
# TC (complexité)

En informatique théorique, et plus précisément en théorie de la complexité, TC est la classe de complexité des problèmes de décision reconnus par des circuits avec seuil. Ce sont des circuits booléens avec des portes ET, des portes OU et des portes qui calculent la majorité (en). Pour un entier i fixé, la classe $TC^i$ est la classe des langages reconnus par une famille de circuits avec seuil de profondeur $O(\log ^{i}n)$, de taille polynomiale, et avec arité non bornée. La classe TC est

    ${\mbox{TC}}=\bigcup _{i\geq 0}{\mbox{TC}}^{i}.$

## Relations avec NC et AC

Les relations entre TC, les hiérarchies NC et AC se résument par :

    ${\mbox{NC}}^{i}\subseteq {\mbox{AC}}^{i}\subseteq {\mbox{TC}}^{i}\subseteq {\mbox{NC}}^{i+1}.$

En particulier, on sait que

    ${\mbox{NC}}^{0}\subsetneq {\mbox{AC}}^{0}\subsetneq {\mbox{TC}}^{0}\subseteq {\mbox{NC}}^{1}.$

La première inclusion est stricte car $NC^0$ ne peut pas calculer une fonction qui dépend de toutes les bits d'entrées. Ainsi, choisir un problème dans $AC^0$ qui de tous les bits sépare les deux classes (par exemple, la fonction ou). L'inclusion stricte $AC^0$ ⊊ $TC^0$ provient du fait que les fonctions parité et majorité, qui sont dans $TC^0,$ ne sont pas dans $AC^0^,.$

Des inclusions précédentes, on a NC = AC = TC.

