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 $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[modifier | modifier le code]

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⁰ 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⁰^[1]^,^[2].

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

Bibliographie[modifier | modifier le code]

(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[modifier | modifier le code]

↑ Merrick Furst, James B. Saxe et Michael Sipser, « Parity, circuits, and the polynomial-time hierarchy », Mathematical Systems Theory, vol. 17, n^o 1,‎ 1984, p. 13-27 (DOI 10.1007/BF01744431, MR 738749).
↑ Johan Håstad, « Almost Optimal Lower Bounds for Small Depth Circuits », Randomness and Computation, JAI Press, vol. 5,‎ 1989, p. 6-20 (ISBN 0-89232-896-7, lire en ligne).

Portail de l'informatique théorique

[1] Merrick Furst, James B. Saxe et Michael Sipser, « Parity, circuits, and the polynomial-time hierarchy », Mathematical Systems Theory, vol. 17, n^o 1,‎ 1984, p. 13-27 (DOI 10.1007/BF01744431, MR 738749).

[2] Johan Håstad, « Almost Optimal Lower Bounds for Small Depth Circuits », Randomness and Computation, JAI Press, vol. 5,‎ 1989, p. 6-20 (ISBN 0-89232-896-7, lire en ligne).

[1]

[2]