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

14

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 ixEuxEu¯
  2. adicione um vértice para cada cláusula Cj
  3. adicione uma aresta para cada par (xEu,xEu¯)
  4. adicione uma aresta do vértice (ou ¯ x i ) a cada vértice que representa uma cláusula que o contémxEuxEu¯
  5. adicionar bordas entre duas variáveis consecutivos (x1,x2),(x2,x3),...,(xn,x1)

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 ? (xEu,xEu+1)
Vor
fonte
1
Apenas para o caso de alguém procurar o artigo em que mostra dureza do Planar 1-em-3SAT (versão menos forte). Aqui está um link: dl.acm.org/citation.cfm?doid=1137856.1137859 A partir da prova deles, podemos ver que o requisito de "espinha dorsal" é facilmente atendido.
sud03r

Respostas:

8

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 .

A.Schulz
fonte