Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
NC (complexité)
Résumé
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, qui a travaillé sur le sujet.
Par exemple, le (problème de décision associé au calcul du) produit matriciel est dans NC.
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.
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 AC0), multiplication de deux entiers dans NC1 mais pas dans AC0;
addition de deux matrices, multiplication de deux matrices ;
calculer un couplage maximal dans un graphe ;
La fonction parité de n bits est dans NC1 : 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). La fonction parité n'est pas dans AC0.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.