Uma variante do SAT Crítico no DP

Um idioma está na classe se houver dois idiomas e modo que$L$$DP$$L1 \in NP$$L2 \in coNP$$L = L1 \cap L2$

Um problema canônico de completo é SAT-UNSAT: dadas duas expressões 3-CNF, e , é verdade que é satisfatório e$DP$$F$$G$$F$$G$ não é?

Também se sabe que o problema Critical SAT é completo: Dada uma expressão de 3-CNF, F é insatisfatória, mas a exclusão de qualquer cláusula a torna satisfatória?$DP$$F$ , é verdade que$F$

Estou considerando a seguinte variante do problema Critical SAT: Dada uma expressão 3-CNF $F$, é verdade que $F$ é satisfatório, mas adicionar qualquer cláusula 3 (de $F$ mas usando as mesmas variáveis ​​que $F$ ) a torna insatisfatória? Mas eu não conseguir encontrar uma redução do SAT-UNSAT ou mesmo provar que é $NP$ ou $coNP$ duro.

Minha pergunta: essa variante é DP-complete?

Obrigado por suas respostas.

[Eu fiz isso em uma resposta adequada porque alguém deu -1]

Se for permitida a inclusão de qualquer cláusula, o idioma estará vazio - claramente para qualquer fórmula satisfatória você pode adicionar uma cláusula 3 com c composta por variáveis ​​que não aparecem em F : F ∪ { c } será satisfatório.$F$$c$$F$$F \cup \{ c \}$

Se as cláusulas adicionadas devem usar variáveis ​​de , o idioma está em P.$F$

A justificação é a seguinte:

Tomar qualquer , ou seja, F ∈ S A T e para qualquer 3-cláusula c nas variáveis de F , F ∪ { c } ∈ L N S A T . Say c = l 1 ∨ l 2 ∨ l 3 ∉ F , onde l i é um literal. Como F ∪ { c } é UNSAT, todos os modelos de F devem ter l $F \in L$$F \in SAT$$c$$F$$F \cup \{c\} \in UNSAT$$c = l_1 \lor l_2 \lor l_3 \notin F$$l_i$$F \cup \{ c \}$$F$ (para i = 1 , 2 , 3 ) - porque se algum modelo tivesse, por exemplo, l 1 = 1 , então ele satisfaria c e então F ∪ { c } . Agora, suponha que exista outra cláusula c ′ que seja exatamente igual a c , mas com um ou mais literais invertidos e tal que c ′ ∉ F , diga c ′ = ¬ l 1 ∨ l 2 ∨ l $l_i=0$$i=1,2,3$$l_1=1$$c$$F \cup \{c\}$$c'$$c$$c' \notin F$$c' = \neg l_1 \lor l_2 \lor l_3$. Então, pelo mesmo argumento, todos os modelos de devem ter l 1 = 1 . Assim, a condição necessária para a F ∈ L é que, para cada cláusula c ∈ F há exatamente 6 outras cláusulas em F que usam as três variáveis de c - permite chamar esses subconjuntos 7 cláusula de F blocos . Observe que cada bloco implica uma atribuição única e satisfatória para suas variáveis. Quando essa condição necessária é satisfeita, F é exclusivamente satisfatório ou insatisfatório. Os dois casos podem ser distinguidos testando se as atribuições implícitas pelos blocos de $F$$l_1 = 1$$F \in L$$c \in F$$F$$c$$F$ $F$$F$ confronto, o que pode ser feito claramente em tempo linear.

Posso propor uma resposta para minha própria pergunta, graças aos seus comentários: a variante do Critical SAT está em P.

Vamos chamar de "Problema 1" a variante do SAT Crítico: dada uma expressão 3-CNF , é verdade que F é satisfatório, mas adicionar qualquer cláusula de F a torna insatisfatória?$F$$F$$F$

E "Problema 2": Dada uma expressão 3-CNF , é verdade que F contém todas as cláusulas implícitas e possui um modelo único?$F$$F$

Dada uma fórmula 3-CNF, .$F$

Se é um exemplo sim de problema 2, então qualquer a cláusula de F não está implícito F e depois cobre a única possível atribuição satisfatório para F . A adição de uma cláusula a F torna-a insustentável. F é consequentemente uma instância sim do problema 1.$F$$F$$F$$F$$F$$F$

Se é uma instância não de problema 2, então: Caso 1: existe uma cláusula de F que está implícito F . A adição desta cláusula a F não altera sua satisfação. F é conseqüentemente um exemplo de problema nenhum. Caso 2: F contém todas as cláusulas que implica, mas é insatisfatório. F é conseqüentemente um exemplo de problema 1. O caso 3: F contém todas as cláusulas que implica, mas possui pelo menos 2 modelos diferentes. Como o comentário de Kaveh enfatiza, «assuma que os modelos diferem na variável p, então adicionar uma cláusula que a contenha não mudará a satisfação. » F é conseqüentemente um exemplo de problema 1.$F$$F$$F$$F$$F$$F$$F$$F$$F$

Então, é uma instância sim do problema 1, se F for uma instância sim do problema 2.$F$$F$

O problema 2 é claramente um problema P (por exemplo, é uma instância sim do problema 2 se houver exatamente ($F$ =n(n-1)(n-2$\binom{n}{3}$ cláusulas de F sem literais opostas em nenhuma delas -né o número de variáveis). O mesmo acontece com o problema 1.$\frac{n(n-1)(n-2)}{3}$$n$