NC (classe de complexitat)

En teoria de la complexitat computacional, la classe de complexitat NC (la classe de Nick) és el conjunt dels problemes de decisió que poden ser resolts per mig de computació paralela en un número polinòmic de processadors en temps polilogarítmico. Dit d'una atra forma, un problema està en NC si existixen constants c i k tals que el problema pot ser resolt en temps O((log n)^c) utilisant O(n^k) processadors paralels.

De la mateixa manera que els problemes de P poden vore's com els problemes resolubles en una màquina seqüencial, els de NC poden vore's com aquells que poden resoldre's eficientemente en una màquina paralela. NC és subconjunt de P ya que les màquines paraleles poden simular-se en màquines seqüencials. No s'ha determinat si NC = P, pero es pensa que són classes diferents, lo que voldria dir que alguns problemes no poden ser millorats usant una màquina paralela. De la mateixa manera que la classe NP-complet pot vore's com la classe de problemes "segurament sense solució eficient", la classe P-complet pot vore's com la classe de problemes "segurament no paralelizables".

Stephen Cook va falcar el terme NC (Classe de Nick) en honor a Nick Pippenger, qui ha investigat els circuits de profunditat polilogarítmica i tamany polinòmic.

Referències

• Greenlaw, Raymond, James Hoover, and Walter Ruzzo. Limits To Parallel computation; P-Completeness Theory. ISBN 0-19-508591-4