b"\n_START_ARTICLE_\nNC (Complexitat)\n_START_PARAGRAPH_\nEn teoria de la complexitat, la classe de complexitat NC (la Classe d'en Nick o NIck's class) \xc3\xa9s el conjunt de problemes de decisi\xc3\xb3 que espoden resoldre en un temps polilogar\xc3\xadtmic en un computador paral\xc2\xb7lel amb un nombre polin\xc3\xb2mic de processadors. Dit d'una d'altra manera, un problema \xc3\xa9s a NC si existeixen unes constants c i k tals que es pot solucionar en temps O(log\xe1\xb6\x9c n) fent servir un nombre O(n\xe1\xb5\x8f) de processadors paral\xc2\xb7lels._NEWLINE_Tamb\xc3\xa9 es pot definir NC com el conjunt de problemes de decisi\xc3\xb3 que poden ser solucionats per un circuit Boole\xc3\xa0 d'una profunditat polilogar\xc3\xadtmica i un nombre de portes polin\xc3\xb2mic._NEWLINE_La classe va ser batejada per Stephen Cook en honor a Nick Pippenger, que havia treballat en aquesta mena de problemes._NEWLINE_Es pot assumir que el computador paral\xc2\xb7lel de la definici\xc3\xb3 \xc3\xa9s un computador paral\xc2\xb7lel PRAM, aix\xc3\xb2 \xc3\xa9s, que est\xc3\xa0 format per un seguit de processadors que poden accedir a una mem\xc3\xb2ria principal comuna en un temps constant. La definici\xc3\xb3 de la classe no es veu afectada per com es gestionen els accessos simultanis a un bit per part de diferents processadors._NEWLINE_De la mateixa manera que la classe P es pot veure com la classe dels problemes tractables, la classe NC es pot veure com els problemes que es poden tractar en ordinadors paral\xc2\xb7lels."