Condiciones de planaridad para SAT Planar 1 en 3

Planar 3SAT es NP-completo. Una instancia plana de 3SAT es una instancia de 3SAT para la cual el gráfico creado con las siguientes reglas es plano:

1. agregue un vértice para cada y$x_i$$\bar{x_i}$
2. agregue un vértice para cada cláusula$C_j$
3. añadir una ventaja para todos los par$(x_i,\bar{x_i})$
4. agregue un borde desde el vértice (o ) a cada vértice que representa una cláusula que lo contiene$x_i$$\bar{x_i}$
5. agregue bordes entre dos variables consecutivas $(x_1,x_2),(x_2,x_3),...,(x_n,x_1)$

En particular, la regla 5 construye una "columna vertebral" que divide las cláusulas en dos regiones distintas.

El SAT Planar 1 en 3 también tiene NP completo.

Pero para el SAT planar 1 en 3, ¿se definen las condiciones de planaridad de la misma manera que en Planar 3SAT? En particular, ¿podemos suponer que hay una columna vertebral que une las variables ? $(x_i,x_{i+1})$

Sí tu puedes. En realidad, incluso puedes demostrar que algo más fuerte es cierto. El problema conocido como Positivo Planar 1-en-3-SAT es NP-completo como lo muestran Mulzer y Rote .

En esta versión de 1-en-3-SAT, necesita para cada fórmula de entrada que

• tiene tres variables por cláusula, ninguna de ellas negada
• la gráfica de la fórmula es plana, incluso si agrega la "columna vertebral" entre los vértices variables

La reducción es de Planar 3-SAT .