Complexidade do problema de monotonia (+, 2) SAT?
Para continuar este post , vamos definir o problema Monotone -SAT:(+,2−)(+,2−)
Dada uma fórmula monótona de CNF , em que cada variável aparece exatamente uma vez (como um literal positivo) e uma fórmula monotônica de 2-CNF definida nas mesmas variáveis ​​que , onde todas as variáveis ​​são negadas. É satisfiable?F+F+F−2F2−F+F+F+∧F−2F+∧F2−
Esse problema está completo?
— Xavier Labouze
Isso é NP-completo. De fato, permanece NP-completo quando é restrito a estar no formato 3-CNF (não apenas CNF).F+F+
A prova é demonstrar que esse problema é pelo menos tão difícil quanto testar a capacidade de três cores de um gráfico. A correspondência é limpa e elegante. Seja um gráfico não direcionado. Introduza as variáveis , para e , para representar uma coloração 3 do gráfico. Aqui significa que atribuímos ao vértice a cor .G=(V,E)G=(V,E)xv,cxv,cv∈Vv∈Vc∈{1,2,3}c∈{1,2,3}xv,cxv,cvvcc
Para representar que cada vértice deve receber pelo menos uma cor, introduziremos as cláusulas para cada vértice . Isso nos dá , ou seja,xv,1∨xv,2∨xv,3xv,1∨xv,2∨xv,3vvF+F+
F+≡⋀v∈V(xv,1∨xv,2∨xv,3).F+≡⋀v∈V(xv,1∨xv,2∨xv,3).
Para representar que nenhum ponto final de uma única aresta pode receber a mesma cor, introduziremos uma cláusula para cada aresta . E, para representar que nenhum vértice pode receber mais de uma cor, introduziremos uma cláusula para cada tal que Seja a fórmula correspondente.¬xu,c∨¬xv,c¬xu,c∨¬xv,c(u,v)∈E(u,v)∈E¬xv,c∨¬xv,c′¬xv,c∨¬xv,c′c≠c′.c≠c′.