NC (complexité)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 pouvant être résolus en temps polylogarithmique avec nombre polynomial de machines en parallèle.

La classe a été nommée par Stephen Cook en l'honneur de Nick Pippenger (en)[1].

Par exemple le produit matriciel est dans NC.

Définition[modifier | modifier le code]

Un problème P est dans NC si il existe deux constantes c et k, telles qu'il est possible de résoudre P en un temps O(\log^c(n)) en utilisant O(n^k) processeurs en parallèle.

On peut donner une définition plus précise grâce aux circuits booléens: pour tout c, la classe NCc est l'ensemble des langages qui peuvent être décidés par une famille de circuit \mathcal{C}_n (où n est la taille de l'entrée) de taille polynomiale en n et de profondeur O(\log^c(n)). NC est alors \cup_{c \geq 1} NC^c.

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

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

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

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

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,‎ 2009 (ISBN 0-521-42426-7) 6.7.1