Accueil🇫🇷Chercher

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 TCi est la classe des langages reconnus par une famille de circuits avec seuil de profondeur , de taille polynomiale, et avec arité non bornée. La classe TC est

Relations avec NC et AC

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

En particulier, on sait que

La première inclusion est stricte car NC0 ne peut pas calculer une fonction qui dépend de toutes les bits d'entrées. Ainsi, choisir un problème dans AC0 qui de tous les bits sépare les deux classes (par exemple, la fonction ou). L'inclusion stricte AC0TC0 provient du fait que les fonctions parité et majorité, qui sont dans TC0, ne sont pas dans AC0[1] - [2].

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

Bibliographie

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

Notes et références

  1. Merrick Furst, James B. Saxe et Michael Sipser, « Parity, circuits, and the polynomial-time hierarchy », Mathematical Systems Theory, vol. 17, no 1, , 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, , p. 6-20 (ISBN 0-89232-896-7, lire en ligne).
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.