NC (complexité)

En théorie de la complexité, un domaine de l'informatique théorique, NC (pour Nick's class) est une classe de complexité faisant intervenir le parallélisme. C'est l'ensemble des problèmes de décision décidés en temps polylogarithmique par un nombre polynomial de machines en parallèle. Elle correspond aux problèmes considérés comme facilement traitables par une architecture parallèle. La classe a été nommée par Stephen Cook[1],[2] en l'honneur de Nick Pippenger, qui a travaillé sur le sujet[3],[4].

Par exemple, le (problème de décision associé au calcul du) produit matriciel est dans NC.

Définition

Un problème A est dans NC s'il existe deux constantes c et k telles qu'il est possible de résoudre A en un temps ${\displaystyle O(\log ^{c}(n))}$ en utilisant ${\displaystyle O(n^{k})}$ processeurs en parallèle. On peut donner une définition plus précise grâce aux circuits booléens. L'idée est que deux portes logiques peuvent calculer leur sortie en parallèle. Ainsi, le nombre de portes logiques est — grosso modo — le nombre de processeurs. La profondeur du circuit représente le temps d'exécution. Plus précisément, pour tout ${\displaystyle c}$, on définit d'abord la classe NC^c comme l'ensemble des langages décidés par une famille de circuits ${\displaystyle ({\mathcal {C}}_{n})_{n\in \mathbb {N} }}$ (où ${\displaystyle n}$ est la taille de l'entrée) dits uniformes (c'est-à-dire que l'on peut calculer effectivement ${\displaystyle {\mathcal {C}}_{n}}$ à partir de l'entier ${\displaystyle n}$) de taille polynomiale en ${\displaystyle n}$ et de profondeur ${\displaystyle O(\log ^{c}(n))}$. La classe NC est alors ${\displaystyle \cup _{c\geq 1}NC^{c}}$.

Ces deux définitions sont équivalentes[4].

Exemples de problèmes dans NC

Les problèmes de décisions associés aux problèmes de calcul suivants sont dans NC :

• addition de deux entiers (plus précisément dans AC^0), multiplication de deux entiers dans NC^1 mais pas dans AC^0;
• addition de deux matrices, multiplication de deux matrices ;
• calculer un couplage maximal dans un graphe^[réf. nécessaire] ;
• La fonction parité de n bits est dans NC^1 : on construit, façon diviser pour régner, un arbre binaire de porte XOR, qui peuvent se réécrire avec des portes NOT, AND et OR et ainsi obtenir un circuit de hauteur O(log n)[5]. La fonction parité n'est pas dans AC^0.
• En 1987, Buss a démontré que l'évaluation d'une formule (c'est un cas particulier du problème de l'évaluation d'un circuit booléen, car une formule booléenne est un circuit booléen qui est un arbre) est complet pour la classe ALOGTIME avec des réductions en temps logarithmique (ces classes en temps logarithmiques sont définies avec des machines de Turing RAM)[6]. ALOGTIME est égale à NC^1 avec une certaine condition d'uniformité[7].

Relations avec les autres classes

Les relations suivantes sont connues, elles mettent en jeu les classes L, NL et P :

${\displaystyle \mathbf {NC} ^{1}\subseteq \mathbf {L} \subseteq \mathbf {NL} \subseteq \mathbf {AC} ^{1}\subseteq \mathbf {NC} ^{2}\subseteq \mathbf {NC} \subseteq \mathbf {P} .}$

On peut aussi définir la classe AC et des classes AC^i de façon analogue à NC et NC^i sauf que l'arité des portes logiques est non bornée. En fait, comme ${\displaystyle \mathbf {NC} ^{i}\subseteq \mathbf {AC} ^{i}\subseteq \mathbf {NC} ^{i+1}}$, pour tout i, on a[8] : AC = NC.

Ruzzo[9] a montré que NC est exactement la classe des problèmes de décision décidés par une machine de Turing alternante en espace log n avec un nombre d'alternances (log n)^O(1), c'est-à-dire que NC = STA(log n, *, (log n)^O(1)) où STA(s(n), t(n), a(n)) est la classe des problèmes de décision décidés par une machine de Turing alternante en espace s(n), temps t(n) et alternances a(n)[10].

On ne sait pas si NC est égal à P ou pas. Comme le précise Arora et Barak[4], on ne sait pas séparer NC^1 et la hiérarchie polynomiale PH.

Problème ouvert au sujet de l'effondrement

Une question importante en théorie de la complexité est de savoir si les inclusions ${\displaystyle {\textbf {NC}}^{1}\subseteq {\textbf {NC}}^{2}\subseteq \cdots }$ de la hiérarchie NC sont stricts ou non. Papadimitriou a observé que si NC^i = NC^i+1 pour un certain i, alors NC^i = NC^j pour tout j ≥ i, et ainsi, NC^i = NC. Cette observation s'appelle un effondrement de la hiérarchie NC car une seule égalité dans la chaine d'inclusions

${\displaystyle {\textbf {NC}}^{1}\subseteq {\textbf {NC}}^{2}\subseteq \cdots }$

implique que toute la hiérarchie NC s'effondre au niveau i. Ainsi, il y a deux possibilités :

1. ${\displaystyle {\textbf {NC}}^{1}\subset \cdots \subset {\textbf {NC}}^{i}\subset ...\subset {\textbf {NC}}^{i+j}\subset \cdots {\textbf {NC}}}$
2. ${\displaystyle {\textbf {NC}}^{1}\subset \cdots \subset {\textbf {NC}}^{i}=...={\textbf {NC}}^{i+j}=\cdots {\textbf {NC}}}$

Les chercheurs pensent^[réf. nécessaire] qu'à priori les inclusions sont strictes (1) mais il n'y a pas de démonstrations.

Théorème de Barrington

Barrington a démontré que la classe NC non uniforme correspond aux problèmes décidés par des programmes branchées définies de la façon suivante.

Lien externe

(en) La classe NC sur le Complexity Zoo

Notes et références

1. (en) « Towards a complexity theory of synchronous parallel computation. », L'Enseignement mathématique, vol. 27,‎ 1981 (lire en ligne)
2. (en) Stephen A. Cook, « A taxonomy of problems with fast parallel algorithms », Information and Control, vol. 64, n^o 1,‎ 1^er janvier 1985, p. 2–22 (ISSN 0019-9958, DOI 10.1016/S0019-9958(85)80041-3, lire en ligne)
3. (en) Nicholas Pippenger, « On simultaneous resource bounds », 20th Annual Symposium on Foundations of Computer Science (sfcs 1979),‎ 1979, p. 307–311 (ISSN 0272-5428, DOI 10.1109/SFCS.1979.29, lire en ligne)
4. (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7) 6.7.1.
5. (en) « Cours - Lecture 2: The Complexity of Some Problems » [PDF].
6. Samuel R. Buss, « The Boolean formula value problem is in ALOGTIME », sur www.math.ucsd.edu, janvier 1987 (consulté le 5 mai 2017)
7. (en) « Complexity Zoo:N - Complexity Zoo », sur complexityzoo.uwaterloo.ca (consulté le 29 octobre 2018)
8. (en) « Boolean Functions and Computation Models - Springer », sur link.springer.com (consulté le 9 juin 2016).
9. (en) Walter L. Ruzzo, « On uniform circuit complexity », Journal of Computer and System Sciences, vol. 22, n^o 3,‎ 1^er juin 1981, p. 365–383 (DOI 10.1016/0022-0000(81)90038-6, lire en ligne, consulté le 30 octobre 2017).
10. (en) Dexter C. Kozen, Theory of Computation, Springer Publishing Company, Incorporated, 2010 (ISBN 1849965714 et 9781849965712, lire en ligne).