NC (complexité)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant l’informatique théorique
Cet article est une ébauche concernant l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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 en l'honneur de Nick Pippenger (en)[1].

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

Définition[modifier | modifier le code]

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 en utilisant 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 , on définit d'abord la classe NCc comme l'ensemble des langages décidés par une famille de circuits (où est la taille de l'entrée) dits uniformes (c'est-à-dire que l'on peut calculer effectivement à partir de l'entier ) de taille polynomiale en et de profondeur . La classe NC est alors .

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

Exemples de problèmes dans NC[modifier | modifier le code]

Les problèmes de décisions associés aux problèmes de calcul suivant sont dans NC ː

  • addition de deux entiers, multiplication de deux entiers
  • addition de deux matrices, multiplication de deux matrices
  • Calculer un couplage maximal dans un graphe[réf. nécessaire]

Relations avec les autres classes[modifier | modifier le code]

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

On peut aussi définir la classe AC et des classes ACi de façon analogue à NC et NCi sauf que l'arité des portes logiques est non bornées. En fait, comme , pour tout i, on a[2]: AC = NC.

Lien externe[modifier | modifier le code]

(en) La classe NC sur le Complexity Zoo

Notes et références[modifier | modifier le code]

  1. a et b (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A modern Approach, Cambridge University Press, (ISBN 0-521-42426-7) 6.7.1
  2. « Boolean Functions and Computation Models - Springer », sur link.springer.com (consulté le 9 juin 2016)