CC (complejidad)
En la teoría de la complejidad computacional , CC (Comparator Circuits) es la clase de complejidad que contiene problemas de decisión que pueden resolverse mediante circuitos comparadores de tamaño polinomial .
Los circuitos comparadores son redes de clasificación en las que se dirige cada puerta del comparador, cada cable se inicializa con una variable de entrada, su negación o una constante, y uno de los cables se distingue como el cable de salida.
El problema más importante que se completa para CC es una variante de decisión del problema del matrimonio estable .
Un circuito comparador es una red de cables y puertas. Cada puerta del comparador, que es un borde dirigido que conecta dos cables, toma sus dos entradas y las emite en orden ordenado (el valor más grande termina en el cable al que apunta el borde). La entrada a cualquier cable puede ser una variable, su negación o una constante. Uno de los cables se designa como el cable de salida. La función calculada por el circuito se evalúa inicializando los cables de acuerdo con las variables de entrada, ejecutando las puertas del comparador en orden y emitiendo el valor transportado por el cable de salida.
El problema del valor del circuito comparador (CCVP) es el problema de evaluar un circuito comparador dada una codificación del circuito y la entrada al circuito. La clase de complejidad CC se define como la clase de espacio de registro de problemas reducible a CCVP. [1] Una definición equivalente [2] es la clase de problemas AC 0 reducible a CCVP.
Como ejemplo, se puede usar una red de clasificación para calcular la mayoría al designar el cable central como un cable de salida:
