NC (Complexitat)

En teoria de la complexitat, la classe de complexitat NC (la Classe d'en Nick o NIck's class) és el conjunt de problemes de decisió que es poden resoldre en un temps polilogarítmic en un computador paral·lel amb un nombre polinòmic de processadors. Dit d'una d'altra manera, un problema és a NC si existeixen unes constants c i k tals que es pot solucionar en temps O(log^c n) fent servir un nombre O(n^k) de processadors paral·lels.^[1][2]

També es pot definir NC com el conjunt de problemes de decisió que poden ser solucionats per un circuit Booleà d'una profunditat polilogarítmica i un nombre de portes polinòmic.

La classe va ser batejada per Stephen Cook en honor de Nick Pippenger, que havia treballat en aquesta mena de problemes.^[3]

Es pot assumir que el computador paral·lel de la definició és un computador paral·lel PRAM, això és, que està format per un seguit de processadors que poden accedir a una memòria principal comuna en un temps constant. La definició de la classe no es veu afectada per com es gestionen els accessos simultanis a un bit per part de diferents processadors.

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·lels.^[4]

Relació amb d'altres classes

NC és un subconjunt de la classe P, ja que un computador paral·lel es pot simular amb un computador seqüencial en temps polinòmic. No se sap, però, si P = NC, però se suposa que això no és cert, significant que hi ha problemes que son inherentment seqüencials i que no s'obté cap benefici paral·lelitzant-los.

De la mateixa manera que la classe NP-complet es veu com la classe de problemes probablement intractables, la classe P-complet es pot veure com la classe els problemes probablement no paral·lelitzables (o inherentment seqüencials).

NCⁱ és la classe dels problemes decisió que es poden resoldre amb un circuit booleà amb un nombre de portes polinòmic de dues entrades i profunditat O(logⁱ n) o la classe de problemes que es poden resoldre en temps O(logⁱ n) en un computador paral·lel amb un nombre polilogarítmic de processadors. Clarament es te

${\displaystyle {\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots \subseteq {\mathsf {NC}}^{i}\subseteq \cdots {\mathsf {NC}}}}$

Que forma la jerarquia de NC.

La relació d'aquesta classe amb les classes L, NL i AC és la següent:^[5][6]

${\displaystyle {\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {L}}\subseteq {\mathsf {NL}}\subseteq {\mathsf {AC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq {\mathsf {P}}}}$

Les classes NC estan relacionades amb les classes AC, que son similars però amb portes lògiques sense cap fita al fan-in. Per cada i es te:

${\displaystyle {\displaystyle {\mathsf {NC}}^{i}\subseteq {\mathsf {AC}}^{i}\subseteq {\mathsf {NC}}^{i+1}}}$

Com a conseqüència immediata d'això, es dedueix que AC = NC. Se sap que aquestes inclusions son certes per i = 0.

Referències

1. Barry), Cooper, S. B. (S.. Computability theory. Boca Raton: Chapman & Hall/CRC, 2004. ISBN 1584882379. 
2. B., Enderton, Herbert. Computability theory : an introduction to recursion theory. Amsterdam: Academic Press, 2011. ISBN 9780123849588. 
3. Sanjeev., Arora,. Computational complexity : a modern approach. Cambridge: Cambridge University Press, 2009. ISBN 9780521424264. 
4. Raymond., Greenlaw,. Limits to parallel computation : P-completeness theory. Nova York: Oxford University Press, 1995. ISBN 1429406429. 
5. H., Papadimitriou, Christos. Computational complexity. Reading, Mass.: Addison-Wesley, 1994. ISBN 0201530821. 
6. Peter., Clote,. Boolean functions and computation models. Berlín: Springer, 2002. ISBN 3540594361.