Regola di risoluzione completa per 1-in-k SAT

Question

In CNF SAT, ogni clausola (A o B o c o ...) deve contenere almeno un vero letterale.La regola di risoluzione si applica a coppia di clausole che hanno esattamente un opposto letterale.

(A o B o c) e (! A o D o E)=> (B o C o D o E)

Dico che questa regola è completa, nel senso che se una formula è insoddisfacida, posso dimostrarlo applicando la regola esaustiva (su hard istanze, una quantità esponenziale di volte) fino a quando non viene prodotta una clausola vuota.Se una formula ha una soluzione unica, posso applicare la regola fino a quando non viene prodotta ogni clausola unità.

1-IN-K SAT è una variante completa NP dove esattamente una variabile per clausola (A, B, C, ....)= 1 è vera.Dato un paio di clausola con uno opposto letterale, e nessun common letterale, posso anche produrre un terzo:

(A, B, C)= 1 e (! A, D, E)= 1=> (B, C, D, E)= 1

Domanda : questa regola è completa per formule 1-in-k insoddisfacute e in modo unico soddisfattabile?

Answer 1

Stai trattando la risoluzione come se fosse una regola puramente sintattica.Funziona in questo modo con clausole CNF tradizionali perché corrisponde alla regola di base sottostante.Ma una clausola CNF con la limitazione aggiuntiva di un solo letterale consentita di essere vera non corrisponde più a ciò che la regola di risoluzione può essere validamente applicata a.

L'espressione booleana $ (a \ lor b) \ Land (\ lnot {a} \ lor \ lnot {b}) \ Land (\ lnot {a} \ lor b) $ è insoddisfacida come una formula 1-in-k-sab , ma in modo ingenuo applicazione della regola di risoluzione produce $ a= false, b= true$ come soluzione (errata).