SAT planar

En informática , el problema de 3-satisfacibilidad planar (abreviado PLANAR 3SAT o PL3SAT ) es una extensión del clásico problema de 3-satisfacibilidad booleano a un grafo de incidencia planar . En otras palabras, pregunta si las variables de una fórmula booleana dada (cuyo grafo de incidencia que consiste en variables y cláusulas puede incrustarse en un plano ) pueden reemplazarse consistentemente por los valores VERDADERO o FALSO de tal manera que la fórmula evalúe VERDADERO . Si este es el caso, la fórmula se llama satisfacible . Por otro lado, si no existe tal asignación, la función expresada por la fórmula es FALSA para todas las asignaciones de variables posibles y la fórmula es insatisfacible . Por ejemplo, la fórmula " a AND NOT b " es satisfacible porque uno puede encontrar los valores a = VERDADERO y b = FALSO, lo que hace que ( a AND NOT b ) = VERDADERO. Por el contrario, " a AND NOT a " es insatisfacible.

Al igual que 3SAT , PLANAR-SAT es NP-completo y se utiliza comúnmente en reducciones .

Definición

Cada problema 3SAT se puede convertir en un gráfico de incidencia de la siguiente manera: Para cada variable , el gráfico tiene un nodo correspondiente , y para cada cláusula , el gráfico tiene un nodo correspondiente Se crea un borde entre la variable y la cláusula siempre que o esté en . Los literales positivos y negativos se distinguen utilizando coloraciones de borde . $estilo de visualización v_{i}}$ $estilo de visualización v_{i}}$ $estilo de visualización c_{j}}$ $c_{j}.$ $(v_{i},c_{j})$ $estilo de visualización v_{i}}$ $estilo de visualización c_{j}}$ $estilo de visualización v_{i}}$ $\lno v_{i}$ $estilo de visualización c_{j}}$

La fórmula es satisfactoria si y solo si hay una manera de asignar VERDADERO o FALSO a cada nodo variable de modo que cada nodo de cláusula esté conectado a al menos un VERDADERO por un borde positivo o FALSO por un borde negativo.

Un grafo planar es un grafo que se puede dibujar en el plano de tal manera que ninguna de sus aristas se cruce entre sí. El 3SAT planar es un subconjunto del 3SAT en el que el grafo de incidencia de las variables y cláusulas de una fórmula booleana es planar. Es importante porque es una variante restringida y sigue siendo NP-completo. Muchos problemas (por ejemplo, juegos y rompecabezas) no pueden representar grafos no planares. Por lo tanto, el 3SAT planar proporciona una forma de demostrar que esos problemas son NP-completos.

Prueba de NP-completitud

El siguiente esquema de prueba sigue la demostración de D. Lichtenstein. ^[1]

De manera trivial, PLANAR 3SAT está en NP . Por lo tanto, es suficiente demostrar que es NP-hard mediante reducción a partir de 3SAT .

Esta prueba hace uso del hecho de que es equivalente a y que es equivalente a . $(\lnot a\lor \lnot b\lor c)\land (a\lor \lnot c)\land (b\lor \lnot c)$ $(a\land b)\leftrightarrow c$ $(a\lor \lnot b)\land (\lnot a\lor b)$ $a\leftrightarrow b$

Primero, dibuje el gráfico de incidencia de la fórmula 3SAT. Como no hay dos variables o cláusulas conectadas, el gráfico resultante será bipartito . Suponga que el gráfico resultante no es plano. Para cada cruce de aristas ( a , c ₁ ) y ( b , c ₂ ), introduzca nueve nuevas variables a ₁ , b ₁ , α , β , γ , δ , ξ , a ₂ , b ₂ , y reemplace cada cruce de aristas con un dispositivo de cruce que se muestra en el diagrama. Consiste en las siguientes cláusulas nuevas:

${\begin{array}{ll}(\lnot a_{2}\lor \lnot b_{2}\lor \alpha )\land (a_{2}\lor \lnot \alpha )\land (b_{2}\lor \lnot \alpha ),&\quad {\text{i.e.,}}\quad a_{2}\land b_{2}\leftrightarrow \alpha \\(\lnot a_{2}\lor b_{1}\lor \beta )\land (a_{2}\lor \lnot \beta )\land (\lnot b_{1}\lor \lnot \beta ),&\quad {\text{i.e.,}}\quad a_{2}\land \lnot b_{1}\leftrightarrow \beta \\(a_{1}\lor b_{1}\lor \gamma )\land (\lnot a_{1}\lor \lnot \gamma )\land (\lnot b_{1}\lor \lnot \gamma ),&\quad {\text{i.e.,}}\quad \lnot a_{1}\land \lnot b_{1}\leftrightarrow \gamma \\(a_{1}\lor \lnot b_{2}\lor \delta )\land (\lnot a_{1}\lor \lnot \delta )\land (b_{2}\lor \lnot \delta ),&\quad {\text{i.e.,}}\quad \lnot a_{1}\land b_{2}\leftrightarrow \delta \\(\alpha \lor \beta \lor \xi )\land (\gamma \lor \delta \lor \lnot \xi ),&\quad {\text{i.e.,}}\quad \alpha \lor \beta \lor \gamma \lor \delta \\(\lnot \alpha \lor \lnot \beta )\land (\lnot \beta \lor \lnot \gamma )\land (\lnot \gamma \lor \lnot \delta )\land (\lnot \delta \lor \lnot \alpha ),&\\(a_{2}\lor \lnot a)\land (a\lor \lnot a_{2})\land (b_{2}\lor \lnot b)\land (b\lor \lnot b_{2}),&\quad {\text{i.e.,}}\quad a\leftrightarrow a_{2},~b\leftrightarrow b_{2}\\\end{array}}$

_Si la arista ( a , c1 ) está invertida en el gráfico original, ( a1 , c1 ) debería estar invertida en el dispositivo de cruce. De manera similar, si la arista ( _b_,c2 ₎está invertida _en el gráfico original, ( b1 , c2 ) debería _estar invertida.

Se puede demostrar fácilmente que estas cláusulas son satisfacibles si y sólo si y . $a\leftrightarrow a_{1}$ $b\leftrightarrow b_{1}$

Este algoritmo demuestra que es posible convertir cada cruce en su equivalente planar utilizando únicamente una cantidad constante de nuevas incorporaciones. Como el número de cruces es polinómico en términos del número de cláusulas y variables, la reducción es polinómica. ^[2]

Variantes y problemas relacionados

3SAT planar con un ciclo variable : aquí, además del gráfico de incidencia, el gráfico también incluye un ciclo que pasa por todas las variables, y cada cláusula está dentro o fuera de este ciclo. El gráfico resultante debe seguir siendo planar. Este problema es NP-completo. ^[1]
- Sin embargo, si el problema se restringe aún más de modo que todas las cláusulas estén dentro del ciclo variable, o todas las cláusulas estén fuera de él, entonces el problema se puede resolver en tiempo polinomial utilizando programación dinámica .
3SAT planar con literales : el gráfico de incidencia bipartito de los literales y las cláusulas también es planar. Este problema es NP-completo. ^[1]
3SAT rectilíneo plano : los vértices del gráfico se representan como segmentos horizontales. Cada variable se encuentra en el eje x , mientras que cada cláusula se encuentra por encima o por debajo del eje x . Cada conexión entre una variable y una cláusula debe ser un segmento vertical. Cada cláusula solo puede tener hasta 3 conexiones con variables y pueden ser todas positivas o todas negativas. Este problema es NP-completo. ^[3]
- 3SAT rectilíneo monótono planar : esta es una variante del 3SAT rectilíneo planar donde las cláusulas por encima del eje x son todas positivas y las cláusulas por debajo del eje x son todas negativas. Este problema es NP-completo ^[4] y sigue siendo NP-completo cuando cada cláusula que contiene tres variables tiene dos variables vecinas que son adyacentes en el eje x (es decir, ninguna otra variable aparece horizontalmente entre las variables vecinas). ^[5]
1-en-3SAT planar : este es el equivalente planar de 1-en-3SAT . Es NP-completo. ^[6]
- 1-en-3SAT rectilíneo positivo planar : este es el equivalente planar del 1-en-3SAT positivo . Es NP-completo. ^[7]
NAE 3SAT planar : este problema es el equivalente planar de NAE 3SAT . A diferencia de las otras variantes, este problema se puede resolver en tiempo polinomial . La prueba se realiza mediante reducción a corte máximo planar . ^[8]
Circuito planar SAT : esta es una variante del circuito SAT en la que el circuito, que calcula la fórmula SAT, es un grafo acíclico dirigido planar . Nótese que este es un grafo diferente al grafo de adyacencia de la fórmula. Este problema es NP-completo. ^[9]

Reducciones

Rompecabezas de lógica

La reducción a partir de SAT planar es un método comúnmente utilizado en pruebas de NP-completitud de acertijos lógicos. Algunos ejemplos de estos incluyen Fillomino , ^[10] Nurikabe , ^[11] Shakashaka , ^[12] Tatamibari , ^[13] y Tentai Show . ^[14] Estas pruebas implican la construcción de dispositivos que pueden simular cables que transportan señales (valores booleanos), puertas de entrada y salida, divisores de señales, puertas NOT y puertas AND (u OR) para representar la incrustación planar de cualquier circuito booleano. Dado que los circuitos son planares, no es necesario considerar el cruce de cables.

Plegado plano de cadenas de ángulo fijo

Se trata del problema de decidir si una cadena poligonal con longitudes y ángulos de aristas fijos tiene una configuración plana sin cruces. Se ha demostrado que es fuertemente NP-hard mediante una reducción a partir de la rectilínea monótona planar 3SAT. ^[15]

Partición de longitud mínima de borde

Este es el problema de dividir un polígono en polígonos más simples de modo que la longitud total de todos los bordes utilizados en la partición sea lo más pequeña posible.

Cuando la figura es un polígono rectilíneo y debe dividirse en rectángulos, y el polígono no tiene agujeros, entonces el problema es polinómico. Pero si contiene agujeros (incluso agujeros degenerados, puntos únicos), el problema es NP-hard, por reducción de Planar SAT. Lo mismo sucede si la figura es cualquier polígono y debe dividirse en figuras convexas. ^[16]

Un problema relacionado es la triangulación de peso mínimo : encontrar una triangulación con una longitud de arista total mínima. Se ha demostrado que la versión de decisión de este problema es NP-completa mediante una reducción a partir de una variante de Planar 1-in-3SAT. ^[17]

Referencias

^ abc Lichtenstein, David (1 de mayo de 1982). "Fórmulas planares y sus usos". Revista SIAM de informática . 11 (2): 329–343. doi :10.1137/0211025. ISSN 0097-5397.
^ Demaine, Eric (2015). "7. SAT plano". MIT Open CourseWare .
^ Raghunathan, Arvind; Knuth, Donald E. (1992). "El problema de los representantes compatibles". SIAM J. Discrete Math . 5 (3): 422–427. arXiv : cs/9301116 . Código Bibliográfico :1993cs........1116K. doi :10.1137/0405033. S2CID 9974756.
^ De Berg, Mark; Khosravi, Amirali (2010). "Particiones óptimas del espacio binario en el plano". Computing and Combinatorics . Apuntes de clase en informática. Vol. 6196. págs. 216–225. doi :10.1007/978-3-642-14031-0_25. ISBN 978-3-642-14030-3.
^ Agarwal, Pankaj K.; Aronov, Boris; Geft, Tzvika; Halperin, Dan (2021). "Sobre la partición de ensamblajes planos a dos manos con restricciones de conectividad". Actas del Simposio ACM-SIAM 2021 sobre algoritmos discretos (SODA) : 1740–1756. arXiv : 2009.12369 . doi :10.1137/1.9781611976465.105. ISBN 978-1-61197-646-5.
^ Dyer, ME; Frieze, AM (junio de 1986). "Planar 3DM es NP-completo". Journal of Algorithms . 7 (2): 174–184. doi :10.1016/0196-6774(86)90002-7.
^ Mulzer, Wolfgang; Rote, Günter (15 de mayo de 2008). "La triangulación de peso mínimo es NP-hard". Revista de la ACM . 55 (2): 11:1–11:29. arXiv : cs/0601002 . doi :10.1145/1346330.1346336. ISSN 0004-5411. S2CID 1658062.
^ Moret, BME (junio de 1988). "Planar NAE3SAT está en P". Noticias SIGACT . 19 (2): 51–54. doi :10.1145/49097.49099. ISSN 0163-5700. S2CID 17219595.
^ Demaine, Erik (2015). "6. Circuito SAT". YouTube .
^ Yato, Takauki (2003). Complejidad y completitud de la búsqueda de otra solución y su aplicación a los rompecabezas . CiteSeerX 10.1.1.103.8380 .
^ Holzer, Markus; Klein, Andreas; Kutrib, Martin (2004). "Sobre la NP-completitud del rompecabezas del lápiz NURIKABE y sus variantes" (PDF) . Actas de la 3.ª Conferencia internacional sobre diversión con algoritmos . S2CID 16082806. Archivado desde el original (PDF) el 2020-02-11.
^ Demaine, Erik D.; Okamoto, Yoshio; Uehara, Ryuhei; Uno, Yushi (2014), "Complejidad computacional y un modelo de programación entera de Shakashaka" (PDF) , IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences , E97-A (6): 1213–1219, Bibcode :2014IEITF..97.1213D, doi :10.1587/transfun.E97.A.1213, hdl : 10119/12147
^ Adler, Aviv; Bosboom, Jeffrey; Demaine, Erik D.; Demaine, Martín L.; Liu, Quanquan C.; Lynch, Jayson (7 de mayo de 2020). "Tatamibari es NP-completo". arXiv : 2003.08331 [cs.CC].
^ Fertin, Guillaume; Jamshidi, Shahrad; Komusiewicz, Christian (junio de 2015). "Hacia una guía algorítmica de las galaxias espirales". Ciencias de la computación teórica . 586 : 26–39. doi : 10.1016/j.tcs.2015.01.051 . S2CID 766372 . Consultado el 18 de agosto de 2021 .
^ Demaine, Erik D.; Eisenstat, Sarah (2011). "El aplanamiento de cadenas de ángulos fijos es fuertemente NP-difícil". En Dehne, Frank; Iacono, John; Sack, Jörg-Rüdiger (eds.). Algoritmos y estructuras de datos . Apuntes de clase en informática. Vol. 6844. Springer Berlin Heidelberg. págs. 314–325. doi :10.1007/978-3-642-22300-6_27. ISBN 9783642223006.
^ Lingas, Andrzej; Pinter, Ron Y.; Rivest, Ronald L.; Shamir, Adi (1982). "Partición de polígonos rectilíneos por longitud mínima de arista" (PDF) . Proc. 20th Allerton Conf. Commun. Control Comput : 53–63.
^ Mulzer, Wolfgang; Rote, Günter (mayo de 2008). "La triangulación de peso mínimo es NP-hard". J. ACM . 55 (2): 11:1–11:29. arXiv : cs/0601002 . doi :10.1145/1346330.1346336. ISSN 0004-5411. S2CID 1658062.