¿Están los circuitos AND y OR P completos?

21

La compuerta AND & OR es una compuerta que recibe dos entradas y devuelve su AND y su OR. ¿Los circuitos hechos solo con la compuerta AND & OR, sin fanout, son capaces de hacer cálculos arbitrarios? Más precisamente, ¿el espacio de registro de cálculo del tiempo polinómico es reducible a los circuitos AND y OR?

Mi motivación para este problema es bastante extraña. Como se describe aquí , esta pregunta es importante para el cálculo dentro del juego de computadora Dwarf Fortress .

Itai Bar-Natan
fuente
2
Dichos circuitos son monótonos y, por lo tanto, están lejos de ser P-completos.
David Harris
3
@David Harris: A primera vista, también lo pensé, ¡pero ese razonamiento no es correcto porque una reducción del espacio logarítmico puede aumentar la entrada con su negación!
Tsuyoshi Ito
2
Puede ser, tenga en cuenta que la evaluación de la fórmula booleana monótona está completa para bajo A C 0 . nortedo1UNAdo0 0
Kaveh

Respuestas:

23

Si no entiendo mal lo que quiere decir con compuerta AND & OR, es básicamente una compuerta de comparación que toma dos bits de entrada e y y produce dos bits de salida x y y x y . Los dos bits de salida x y y x y son básicamente min ( x , y ) y max ( x , y ) .XyXyXyXyXy(X,y)(X,y)

Los circuitos comparadores se construyen componiendo estas compuertas comparadoras juntas pero sin permitir más abanicos que no sean las dos salidas producidas por cada compuerta . Por lo tanto, podemos dibujar circuitos comparadores usando las anotaciones a continuación (de manera similar a cómo dibujamos redes de clasificación).

ingrese la descripción de la imagen aquí

Podemos definir el problema del valor del circuito comparador (CCV) de la siguiente manera: dado un circuito comparador con entradas booleanas especificadas, determinar el valor de salida de un cable designado. Al cerrar este problema de CCV bajo las reducciones de espacio de registro, obtenemos la clase de complejidad CC , cuyos problemas completos incluyen problemas naturales como lex-first maximal match, matrimonio estable, roomate estable.

0 0

Dai Le
fuente
0

(la respuesta no es elegible porque se refiere a puertas AND, OR separadas sin restricción de abanico)

El siguiente artículo es sobre el tema: Autómatas celulares de votación mayoritaria, dinámica de ising y completitud P

Mostramos que en tres o más dimensiones estos sistemas pueden simular circuitos booleanos de puertas AND y OR, y por lo tanto son P-completos . Es decir, predecir el estado de los pasos de tiempo en el futuro es al menos tan difícil como cualquier otro problema que requiera tiempo polinómico en una computadora en serie.

(...)

El problema del valor del circuito monótono, donde las compuertas AND y OR están permitidas pero NO las compuertas no, todavía está P-completo por la siguiente razón: usando las leyes de De Morgan (...), podemos cambiar las negaciones a través de las compuertas hasta que solo afectar las entradas mismas. Por lo tanto, cualquier problema de valor de circuito se puede convertir en un problema de valor de circuito monótono con algunas de las entradas negadas. Este tipo de conversión, de una instancia de un problema a una instancia de otro, se denomina reducción.

Mooncer
fuente
¿Podría por favor elaborar su respuesta? No pude ver la conexión entre "estos sistemas" y los circuitos AND & OR mencionados anteriormente.
Dai Le
He leído el periódico hace 2 años. Está dedicado a P-completitud y circuitos lógicos monótonos. Dejo la interpretación final al lector, porque no puedo recordar detalles ahora. Sin duda, es un buen artículo, especialmente si Itai parece estar confundido. Más: ¿no es el texto en negrita en mi cita la respuesta, que los circuitos lógicos AND / OR son P-completos?
Mooncer
Esta bien, tienes razón. Tal vez deje mi respuesta, tal vez sea útil para alguien.
Mooncer
3
Es un hecho bien conocido que el problema de evaluar circuitos monótonos que consisten en compuertas AND y compuertas OR, donde se permite que cada compuerta tenga un fanout 2 , es P-completo. El problema del circuito mencionado por el póster original impone una restricción de despliegue , y por lo tanto no se sabe que sea P-completo.
Dai Le
2
@vzn La evaluación del circuito está en P. Una referencia del hecho que Dai mencionó es el libro de Cook y Nguyen "Fundamentos lógicos de la complejidad de la prueba".
Yuval Filmus