Come a dimostrare che una versione vincolata di 3SAT in cui nessun letterale può verificarsi più di una volta, è risolvibile in tempo polinomiale?

Question

Sto cercando di capire un incarico (tratto dal libro Algoritmi - da S. Dasgupta, CH Papadimitriou, e UV Vazirani , capitolo 8, problema 8.6a), e sto parafrasando ciò che afferma:

Dato che 3SAT rimane NP-completo anche se limitata alle formule in cui ciascuno appare letterali al massimo due volte, mostrano che se ogni appare letterali al massimo una volta, allora il problema è risolvibile in tempo polinomiale.

Ho tentato di risolvere questo problema separando le clausole in più gruppi:

1. clausole che non avevano alcuna variabile in comune con il resto delle clausole
2. clausole che aveva solo 1 variabile in comune
3. clausole che hanno avuto 2 variabili in comune
4. clausole che hanno avuto tutti i 3 variabili in comune

Il mio ragionamento e ha tentato lungo le linee che il # di tali gruppi è finito (a causa della restrizione imposta di non letterale essere presente più di una volta), e abbiamo potuto cercare di soddisfare il gruppo più ristretto primo (gruppo 4) e quindi sostituire il risultato nei gruppi ristretti minore (3, 2 e poi 1), ma mi sono reso conto che questo non è stato del tutto me sempre da nessuna parte, in quanto questo non si discosta molto dal caso per la versione vincolata di 3SAT in cui ogni letterale può apparire al massimo due volte, che ha dimostrato di essere NP-completo.

Ho provato a cercare on-line per eventuali suggerimenti / soluzioni, ma tutto quello che ho potuto ottenere era questo link , in cui il suggerimento dichiarato non aveva senso sufficiente per me, che sto riproducendo testualmente qui:

Suggerimento: Dal momento che ogni appare letterali al massimo una volta, convertire questo problema a problema 2SAT - tempo quindi polinomiale, se un $ letterale x_i $ appare nella clausola $ C_J $ e il complemento dei $ x_i $ (cioè, $ \ overline {x_i } $) nella clausola $ C_K $, la costruzione di una nuova clausola clausola di $ C_J \ lor \ overline {C_K} $.

Sia $ C_J $ e $ C_K $ avere tre letterali ciascuno - non ho avuto come devo fare per la conversione in 2SAT facendo $ C_J \ lor \ overline $ (o $ \ overline {C_K} {C_J \ Lor C_K} $ se l'ho letto in modo non corretto).

Qualsiasi aiuto sia decifrare il suggerimento, o fornendo un percorso che posso esplorare sarebbe molto apprezzato.

Answer 1

Senza perdita di generalità, si può assumere che ogni variabili appare esattamente una volta positivamente e negativamente esattamente una volta (se una variabile gli appare una volta impostato il valore di soddisfare la clausola e rimuovere la clausola). Possiamo anche assumere che una variabile non compare in una clausola più di una volta (se una variabile appare positivamente e negativamente in una clausola, allora la clausola è soddisfatta e può essere rimosso). Questi non alterano il soddisfacibilità.

Ora usare il regola di risoluzione per eliminare le variabili di uno per uno (dal ogni variabile appare esattamente una volta positivamente e negativamente una volta che questo è un processo deterministico). Se in qualsiasi momento si ottiene la clausola vuota l'insieme di clausole è insoddisfacibile, altrimenti è soddisfacibile. Questo perché:

• risoluzione è un sistema a prova di proposizionale completo (vale a dire se una clausola è logicamente implicata dal set di clausole, allora è derivabile dal set di clausole usando solo la regola di risoluzione),

• una serie di clausole è insoddisfacibile se e solo se implica logicamente la clausola vuota.

Questo algoritmo vorrà tempo polinomiale dal momento che ogni variabile è risolto esattamente una volta. In particolare, ciascuna applicazione della risoluzione ridurrà il numero totale di clausole per uno, quindi il numero di clausole non aumenta. Ad esempio, l'applicazione di risoluzione al $ (x \ lor B) \ terreni (\ overline {x} \ lor C) \ terra \ dots) $ rendimenti $ (B \ lor C) \ terra \ dots $, che ha una clausola di meno rispetto a prima risoluzione. Al contrario, se è stato applicato a un formula 3SAT senza alcuna restrizione sul numero di presenze di ciascun letterale, applicando risoluzione potrebbe causare il numero di clausole di aumentare in modo esponenziale.