condiciones de planeidad para planar 1-en-3 SAT

Question

planar 3SAT es NP-completo. Un ejemplo planar 3SAT es un ejemplo 3SAT para los que la gráfica construida usando las siguientes reglas es planar:

1. añadir un vértice por cada $ x_i $ y $ \ bar {x_i} $
2. añadir un vértice para cada cláusula $ C_J $
3. añadir una arista por cada $ (x_i, \ bar {x_i}) $ par
4. añadir una ventaja desde el vértice $ x_i $ (o $ \ bar {x_i} $) para cada vértice que representan una cláusula que lo contiene
5. añadir bordes entre dos variables consecutivos $ (x_1, x_2), (x_2, x_3), ..., (x_n, x_1) $

En particular, el artículo 5 construye una "columna vertebral" que divide las cláusulas en dos regiones distintas.

planar 1-en-3 SAT es NP-completo, también.

Pero para planar 1-en-3 SAT son las condiciones de planitud definidos en la misma forma que en el planar 3SAT? En particular, podemos asumir que existe una red troncal que vincula las variables $ (x_i, x_ {i + 1}) $?

Answer 1

Sí se puede. En realidad, incluso se puede demostrar que algo más fuerte es cierto. El problema conocimientos como planar positiva 1-en-3-SAT es NP-completo como se muestra por Mulzer Rote y .

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

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

La reducción es del planar 3-SAT .