SAT planar

En informática , el problema de 3-satisfacibilidad planar (abreviado PLANAR 3SAT o PL3SAT ) es una extensión del problema clásico de 3-satisfacibilidad booleana a un grafo de incidencia planar . En otras palabras, pregunta si las variables de una fórmula booleana dada —cuyo grafo de incidencia, compuesto por 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 se evalúe como VERDADERO . Si esto ocurre, la fórmula se denomina satisfacible . Por otro lado, si no existe tal asignación, la función expresada por la fórmula es FALSA para todas las posibles asignaciones de variables y la fórmula es insatisfacible . Por ejemplo, la fórmula " a AND NOT b " es satisfacible porque se pueden encontrar los valores a = VERDADERO y b = FALSO, que hacen que ( a AND NOT b ) = VERDADERO. En cambio, " a AND NOT a " es insatisfacible.      

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

Cada problema 3SAT se puede convertir en un gráfico de incidencia de la siguiente manera: Para cada variable${\displaystyle v_{i}}$, el gráfico tiene un nodo correspondiente${\displaystyle v_{i}}$y para cada cláusula${\displaystyle c_{j}}$, el gráfico tiene un nodo correspondiente${\displaystyle c_{j}.}$ Una ventaja${\displaystyle (v_{i},c_{j})}$se crea entre variables${\displaystyle v_{i}}$cláusula${\displaystyle c_{j}}$cuando sea${\displaystyle v_{i}}$o${\displaystyle \lnot v_{i}}$está en${\displaystyle c_{j}}$Los literales positivos y negativos se distinguen mediante colores de borde .

La fórmula es satisfacible si y solo si existe una manera de asignar VERDADERO o FALSO a cada nodo variable de tal forma que cada nodo de cláusula esté conectado al menos a un VERDADERO mediante una arista positiva o a un FALSO mediante una arista negativa.

Un grafo planar es aquel que puede representarse en el plano de forma que ninguna de sus aristas se cruce. 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, aun así, es NP-completo. Muchos problemas (por ejemplo, juegos y rompecabezas) no pueden representarse mediante grafos no planares. Por lo tanto, el 3SAT planar proporciona una forma de demostrar que estos problemas son NP-difíciles.

El siguiente esbozo de demostración sigue la demostración de D. Lichtenstein. ^{[ 1 ]}

Es trivial que PLANAR 3SAT esté en NP . Por lo tanto, basta con demostrar que es NP-difícil mediante una reducción desde 3SAT .

Esta prueba se basa en el hecho de que${\displaystyle (\lnot a\lor \lnot b\lor c)\land (a\lor \lnot c)\land (b\lor \lnot c)}$es equivalente a${\displaystyle (a\land b)\leftrightarrow c}$y eso${\displaystyle (a\lor \lnot b)\land (\lnot a\lor b)}$es equivalente a${\displaystyle a\leftrightarrow b}$.

_{Primero, dibuje el grafo de} incidencia de la fórmula 3SAT. Dado que no hay dos variables o cláusulas conectadas, el grafo resultante será bipartito . Supongamos que el grafo resultante no es planar. Para cada cruce de aristas ( a , c1 ) y ( b , c2 ₎ , introduzca nueve nuevas variables a1 , _b1 , α , β , γ , δ , ξ , a2 , _{b2 y reemplace cada cruce de aristas con un dispositivo de} cruce que se muestra en el diagrama. Este consta de las siguientes nuevas cláusulas:

$${\displaystyle {\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{es decir,}}\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{es decir,}}\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{es decir,}}\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{es decir,}}\quad \lnot a_{1}\land b_{2}\leftrightarrow \delta \\(\alpha \lor \beta \lor \xi )\land (\gamma \lor \delta \lor \lnot \xi ),&\quad {\text{es decir,}}\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{es decir,}}\quad a\leftrightarrow a_{2},~b\leftrightarrow b_{2}\\\end{array}}}$$

Si la arista ( a , c1 ) está invertida en el grafo original, ( a1 , c1 _{) también} debería estar invertida en el componente de cruce. De manera similar, si la arista ( _{b ,} c2 ) está invertida en el grafo original, ( b1 _, c2 ) _también debería estar invertida.

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

Este algoritmo demuestra que es posible convertir cada cruce en su equivalente planar utilizando solo una cantidad constante de nuevas adiciones. Dado que 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 ]}

• 3SAT planar con un ciclo variable : Aquí, además del grafo de incidencia, el grafo también incluye un ciclo que recorre todas las variables, y cada cláusula se encuentra dentro o fuera de este ciclo. El grafo resultante debe seguir siendo planar. Este problema es NP-completo. ^{[ 1 ]}
  • Sin embargo, si el problema se restringe aún más de manera que todas las cláusulas estén dentro del ciclo de variables, 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 grafo de incidencia bipartito de los literales y las cláusulas también es planar. Este problema es NP-completo. ^{[ 1 ]}
• 3SAT rectilíneo planar : Los vértices del grafo se representan como segmentos horizontales. Cada variable se sitúa sobre el eje x , mientras que cada cláusula se sitúa 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 puede tener hasta 3 conexiones con variables, las cuales pueden ser todas positivas o todas negativas. Este problema es NP-completo. ^{[ 3 ]}
  • 3SAT rectilíneo 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 ]}
• Planar 1-en-3SAT : Este es el equivalente planar de 1-en-3SAT . Es NP-completo. ^{[ 6 ]}
  • SAT positivo rectilíneo planar 1 en 3 : Este es el equivalente planar del SAT positivo 1 en 3. 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 demostración se realiza mediante reducción a corte máximo planar . ^{[ 8 ]}
• SAT de circuito planar : Esta es una variante del SAT de circuito 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 del grafo de adyacencia de la fórmula. Este problema es NP-completo. ^{[ 9 ]}