CC (Complexitat)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/84/Comparator_gate_in_a_comparator_circuit.png/220px-Comparator_gate_in_a_comparator_circuit.png)
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
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
- ↑ 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.