classe de complexitat From Wikipedia, the free encyclopedia
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(logc n) fent servir un nombre O(nk) 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]
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).
NCi é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(logi n) o la classe de problemes que es poden resoldre en temps O(logi n) en un computador paral·lel amb un nombre polilogarítmic de processadors. Clarament es te
Que forma la jerarquia de NC.
La relació d'aquesta classe amb les classes L, NL i AC és la següent:[5][6]
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:
Com a conseqüència immediata d'això, es dedueix que AC = NC. Se sap que aquestes inclusions son certes per i = 0.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.