NC

En théorie de la complexité, un domaine de l'informatique théorique, NC 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.

Texte : extrait de l'article Wikipédia « NC (complexité) », sous licence CC BY-SA 4.0.