CC (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, 4-1992, 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.
| Considerades tractables | |
|---|---|
| Suposadament intractables | UP · NP · NP-complet · NP-hard · co-NP · co-NP-complet · AM · QMA · PH · ⊕P · PP · ♯P · ♯P-complet · IP · PSPACE · PSPACE-complet |
| Considerades intractables | |
| Jerarquia de classes | |
| Families de classes | |
