CC (Complexitat)

Una porta comparador.

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.

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 $\subseteq$ CC $\subseteq$P.

Per aquesta classe es desconeix si esta inclosa a NC o a P-complet.