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 .
cc.complexity-theory
circuit-complexity
Itai Bar-Natan
fuente
fuente
Respuestas:
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 ) .X y x ∧ y x ∨ y x ∧ y x ∨ y ( 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).
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.
fuente
(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
fuente