Condições de planaridade para SAT Planar 1 em 3

O Planar 3SAT é NP-completo. Uma instância 3SAT planar é uma instância 3SAT para a qual o gráfico construído usando as seguintes regras é planar:

1. adicione um vértice para cada e ¯ x $x_i$$\bar{x_i}$
2. adicione um vértice para cada cláusula $C_j$
3. adicione uma aresta para cada par $(x_i,\bar{x_i})$
4. adicione uma aresta do vértice (ou ¯ x i ) a cada vértice que representa uma cláusula que o contém$x_i$$\bar{x_i}$
5. adicionar bordas entre duas variáveis consecutivos $(x_1,x_2),(x_2,x_3),...,(x_n,x_1)$

Em particular, a regra 5 cria um "backbone" que divide as cláusulas em duas regiões distintas.

O SAT 1-em-3 plano também é NP-completo.

Mas para o SAT 1-em-3 planar, as condições de planaridade são definidas da mesma maneira que no Planar 3SAT? Em particular, podemos assumir que existe um backbone que vincula as variáveis ? $(x_i,x_{i+1})$

Sim você pode. Na verdade, você pode até mostrar que algo mais forte é verdade. O problema conhecido como 1-em-3-SAT Planar Positivo é NP-completo, como mostrado por Mulzer e Rote .

Nesta versão do 1-em-3-SAT, você precisa de todas as fórmulas de entrada que

• você tem três variáveis ​​por cláusula, nenhuma delas negada
• o gráfico da fórmula é plano, mesmo se você adicionar o "backbone" entre os vértices variáveis

A redução é do Planar 3-SAT .