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ⁱ est la classe des langages reconnus par une famille de circuits avec seuil de profondeur ${\displaystyle O(\log ^{i}n)}$, de taille polynomiale, et avec arité non bornée. La classe TC est

${\displaystyle {\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 :

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

En particulier, on sait que

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

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

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

Bibliographie

• (en) Heribert Vollmer, Introduction to Circuit Complexity : a uniform approach, Berlin, Springer, 1999, 270 p. (ISBN 3-540-64310-9, lire en ligne)

Notes et références

• Portail de l'informatique théorique

1. TC
2. ISO/TC 292
3. Suite de Fibonacci
4. Michel Rocard
5. Théorie du complot
6. Corrida
7. Marion Cotillard
8. Vitamine B12
9. Circuit booléen
10. Nickel
11. État
12. Cycle en V
13. Multiprotocol Label Switching
14. Tannat
15. Low-tech
16. Norme et standard techniques
17. Ultraviolet
18. Passage à niveau
19. Ford Taunus P6
20. Silicium