En la informática teórica , el problema de satisfacibilidad del circuito (también conocido como CIRCUIT-SAT , CircuitSAT , CSAT , etc.) es el problema de decisión de determinar si un circuito booleano dado tiene una asignación de sus entradas que hace que la salida sea verdadera. [1] En otras palabras, pregunta si las entradas a un circuito booleano dado pueden establecerse consistentemente en 1 o 0 de modo que el circuito salga 1 . Si ese es el caso, el circuito se llama satisfactorio . De lo contrario, el circuito se llama insatisfactorio.En la figura de la derecha, el circuito izquierdo puede satisfacerse configurando ambas entradas en 1 , pero el circuito derecho no es satisfactorio.
CircuitSAT está estrechamente relacionado con el problema de satisfacibilidad booleano (SAT) y, de la misma forma, se ha demostrado que es NP-completo . [2] Es un problema NP-completo prototípico; el teorema de Cook-Levin a veces se prueba en CircuitSAT en lugar de en el SAT y luego se reduce a los otros problemas de satisfacibilidad para probar su NP-completitud. [1] [3] La satisfacibilidad de un circuito que contiene las puertas binarias arbitrarias se pueden decidir a tiempo . [4]
Prueba de NP-Completitud
Dado un circuito y un conjunto satisfactorio de entradas, se puede calcular la salida de cada puerta en tiempo constante. Por tanto, la salida del circuito es verificable en tiempo polinomial. Por tanto, el circuito SAT pertenece a la clase de complejidad NP. Para mostrar la dureza NP , es posible construir una reducción de 3SAT a Circuit SAT.
Suponga que la fórmula 3SAT original tiene variables y operadores (Y, O, NO) . Diseñe un circuito de manera que tenga una entrada correspondiente a cada variable y una puerta correspondiente a cada operador. Conecte las puertas de acuerdo con la fórmula 3SAT. Por ejemplo, si la fórmula 3SAT esel circuito tendrá 3 entradas, una Y, una O y una puerta NO. La entrada correspondiente ase invertirá antes de enviar a una puerta AND con y la salida de la puerta AND se enviará a una puerta OR con
Tenga en cuenta que la fórmula 3SAT es equivalente al circuito diseñado anteriormente, por lo tanto, su salida es la misma para la misma entrada. Por lo tanto, si la fórmula 3SAT tiene una asignación satisfactoria, entonces el circuito correspondiente dará salida a 1 y viceversa. Entonces, esta es una reducción válida y el circuito SAT es NP-hard.
Esto completa la prueba de que Circuit SAT es NP-Complete.
Variantes restringidas y problemas relacionados
Circuito plano SAT
Suponga que se nos da un circuito booleano plano (es decir, un circuito booleano cuyo gráfico subyacente es plano ) que contiene solo puertas NAND con exactamente dos entradas. El circuito plano SAT es el problema de decisión de determinar si este circuito tiene una asignación de sus entradas que hace que la salida sea verdadera. Este problema es NP-completo. [5] De hecho, si se cambian las restricciones de modo que cualquier puerta del circuito sea una puerta NOR , el problema resultante sigue siendo NP-completo. [5]
Circuito UNSAT
El circuito UNSAT es el problema de decisión de determinar si un circuito booleano dado genera una salida falsa para todas las posibles asignaciones de sus entradas. Este es el complemento del problema del circuito SAT y, por lo tanto, es Co-NP-completo .
Reducción de CircuitSAT
La reducción de CircuitSAT o sus variantes se puede utilizar para mostrar la dureza NP de ciertos problemas y nos proporciona una alternativa a las reducciones lógicas binarias y de doble carril. Los artilugios que tal reducción necesita para construir son:
- Un aparato de alambre. Este dispositivo simula los cables del circuito.
- Un artilugio dividido. Este dispositivo garantiza que todos los cables de salida tengan el mismo valor que el cable de entrada.
- Gadgets que simulan las puertas del circuito.
- Un verdadero dispositivo terminador. Este dispositivo se usa para forzar que la salida de todo el circuito sea Verdadera.
- Un artilugio giratorio. Este dispositivo nos permite redirigir los cables en la dirección correcta según sea necesario.
- Un gadget cruzado. Este gadget nos permite tener dos cables cruzados sin interactuar.
Problema de inferencia del buscaminas
Este problema pregunta si es posible localizar todas las bombas con un tablero de Buscaminas . Se ha demostrado que es CoNP-Complete mediante una reducción del problema del circuito UNSAT. [6] Los dispositivos construidos para esta reducción son: cable, split, Y y NO puertas y terminador. [7] Hay tres observaciones cruciales con respecto a estos dispositivos. En primer lugar, el dispositivo dividido también se puede utilizar como dispositivo NOT y como dispositivo de giro. En segundo lugar, la construcción de dispositivos AND y NOT es suficiente, porque juntos pueden simular la puerta NAND universal. Finalmente, dado que podemos simular XOR con tres NAND, y dado que XOR es suficiente para construir un crossover, esto nos da el gadget de crossover necesario.
La transformación de Tseytin
La transformación de Tseytin es una reducción sencilla de Circuit-SAT a SAT . La transformación es fácil de describir si el circuito está completamente construido con puertas NAND de 2 entradas (un conjunto funcionalmente completo de operadores booleanos): asigne a cada red en el circuito una variable, luego para cada puerta NAND, construya la forma normal conjuntiva cláusulas ( v 1 ∨ v 3 ) ∧ ( v 2 ∨ v 3 ) ∧ (¬ v 1 ∨ ¬ v 2 ∨ ¬ v 3 ), donde v 1 y v 2 son las entradas a la puerta NAND y v 3 es la salida . Estas cláusulas describen completamente la relación entre las tres variables. La combinación de las cláusulas de todas las puertas con una cláusula adicional que restringe la variable de salida del circuito a ser verdadera completa la reducción; existe una asignación de las variables que satisfacen todas las restricciones si y solo si el circuito original es satisfactorio, y cualquier solución es una solución al problema original de encontrar entradas que hacen que el circuito salga 1. [1] [8] Lo contrario: que SAT es reducible a Circuit-SAT — sigue trivialmente reescribiendo la fórmula booleana como un circuito y resolviéndola.
Ver también
- Problema de valor de circuito
- Satisfacción del circuito estructurado
- Problema de satisfacción
Referencias
- ↑ a b c David Mix Barrington y Alexis Maciel (5 de julio de 2000). "Lección 7: Problemas NP-Complete" (PDF) .
- ^ Luca Trevisan (29 de noviembre de 2001). "Notas para la lección 23: NP-completitud de Circuit-SAT" (PDF) .
- ↑ Véase también, por ejemplo, la prueba informal que se da enlas notas de la conferencia de Scott Aaronson de su curso Computación cuántica desde Demócrito .
- ^ Sergey Nurk (1 de diciembre de 2009). "Un límite superior O (2 ^ {0.4058m}) para el circuito SAT" .
- ^ a b "Límites inferiores algorítmicos: diversión con pruebas de dureza en el MIT" (PDF) .
- ^ Scott, Allan; Stege, Ulrike; van Rooij, Iris (1 de diciembre de 2011). "Buscaminas puede no ser NP-Complete, pero no obstante es difícil". El inteligente matemático . 33 (4): 5–17. doi : 10.1007 / s00283-011-9256-x . ISSN 1866-7414 .
- ^ Kaye, Richard. Buscaminas es NP-completo (PDF) .
- ^ Marques-Silva, João P. y Luís Guerra e Silva (1999). "Algoritmos de satisfacción en circuitos combinacionales basados en búsqueda de retroceso y aprendizaje recursivo" (PDF) .[ enlace muerto permanente ]