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 cada puerta del comparador está dirigida, 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 está completo para CC es una variante de decisión del problema del matrimonio estable .

Un circuito comparador es una red de cables y compuertas. Cada compuerta comparadora, que es una arista dirigida que conecta dos cables, recibe sus dos entradas y las emite en orden (el valor mayor se encuentra en el cable al que apunta la arista). La entrada a cualquier cable puede ser una variable, su negación o una constante. Uno de los cables se designa como cable de salida. La función calculada por el circuito se evalúa inicializando los cables según las variables de entrada, ejecutando las compuertas comparadoras en orden y emitiendo el valor transportado por el cable de salida.

El problema de valor del circuito comparador (CCVP) consiste en evaluar un circuito comparador dada una codificación del circuito y su entrada. La clase de complejidad CC se define como la clase de problemas reducibles a CCVP. ^{[ 1 ]} Una definición equivalente ^{[ 2 ]} es la clase de problemas reducibles a CCVP ^.

Como ejemplo, se puede utilizar una red de clasificación para calcular la mayoría designando el cable central como cable de salida:

Si el cable central se designa como salida y los cables se anotan con 16 variables de entrada diferentes, entonces el circuito comparador resultante calcula la mayoría. Dado que hay redes de ordenación que se pueden construir en AC ⁰ , esto muestra que la función de mayoría está en CC .

Un problema en CC es CC -completo si todo problema en CC puede reducirse a él mediante una reducción de espacio logarítmico . El problema de valor del circuito comparador (CCVP) es CC -completo.

En el problema del matrimonio estable , hay un número igual de hombres y mujeres. Cada persona clasifica a todos los miembros del sexo opuesto. Un emparejamiento entre hombres y mujeres es estable si no hay hombres y mujeres sin pareja que se prefieran mutuamente sobre sus parejas actuales. Siempre existe un emparejamiento estable. Entre los emparejamientos estables, hay uno en el que cada mujer obtiene al mejor hombre que haya obtenido en cualquier emparejamiento estable; este se conoce como el emparejamiento estable óptimo para la mujer . La versión de decisión del problema del emparejamiento estable es, dadas las clasificaciones de todos los hombres y mujeres, determinar si un hombre y una mujer dados se emparejan en el emparejamiento estable óptimo para la mujer. Aunque el algoritmo clásico de Gale-Shapley no se puede implementar como un circuito comparador, Subramanian ^{[ 3 ]} propuso un algoritmo diferente que muestra que el problema está en CC . El problema también es CC -completo.

Otro problema que es CC -completo es el emparejamiento máximo lexicográficamente primero. ^{[ 3 ]} En este problema, se nos da un grafo bipartito con un orden en los vértices y una arista. El emparejamiento máximo lexicográficamente primero se obtiene emparejando sucesivamente vértices de la primera bipartición con los vértices mínimos disponibles de la segunda bipartición. El problema pregunta si la arista dada pertenece a este emparejamiento.

Scott Aaronson demostró que el modelo de guijarros es CC -completo. ^{[ 4 ]} En este problema, se nos da un número inicial de guijarros (codificado en unario ) y una descripción de un programa que puede contener solo dos tipos de instrucciones: combinar dos pilas de tamaños${\displaystyle y}$y${\displaystyle z}$para obtener una nueva pila de tamaño${\displaystyle y+z}$o dividir una pila de tamaño${\displaystyle y}$en montones de tamaño${\displaystyle \lceil y/2\rceil }$y${\displaystyle \lfloor y/2\rfloor }$El problema consiste en determinar si hay guijarros en un montón determinado tras ejecutar el programa. Utilizó esto para demostrar que el problema de determinar si alguna bola alcanza un vértice de destino específico en un dispositivo similar a Digi-Comp II también es CC -completo.

El problema de evaluación del circuito comparador se puede resolver en tiempo polinomial, por lo que CC está contenido en P ("universalidad del circuito"). Por otro lado, los circuitos comparadores pueden resolver la alcanzabilidad dirigida, ^{[ 3 ]} por lo que CC contiene NL . Hay un mundo relativizado en el que CC y NC son incomparables, ^{[ 2 ]} por lo que ambas contenciones son estrictas.

• Zoológico de la complejidad : CC