CC (Complexitat)
classe de complexitat
En teoria de la complexitat, la classe de complexitat CC (circuits comparadors, comparator circuits) és el conjunt dels problemes de decisió que poden ser resolts amb circuits comparadors de mida polinòmica.[1][2]
Un circuit comparador és una xarxa de fils i portes. Cada porta comparador, que és una aresta dirigida connectant dos fils, agafa dues entrades i les treu en ordre. Cada entrada pot ser una variable, la seva negada o una constant. Un els fils s'etiqueta com el fil de sortida.
També es pot definir la classe CC com la dels problemes en espai logarítmic reduïbles a la classe CCVP.
Relació amb d'altres classes modifica
Només es coneix la relació amb les classes NL CC P.[1]
Per aquesta classe es desconeix si esta inclosa a NC o a P-complet.
Referències modifica
- ↑ 1,0 1,1 Mayr, Ernst W.; Subramanian, Ashok «The complexity of circuit value and network stability». Journal of Computer and System Sciences, 44, 2, 1992-04, pàg. 302–323. DOI: 10.1016/0022-0000(92)90024-d. ISSN: 0022-0000.
- ↑ Cook, Stephen A.; Filmus, Yuval; Le, Dai Tri Man «The Complexity of the Comparator Circuit Value Problem». arXiv:1208.2721 [cs], 13-08-2012.