Come funziona l'algoritmo Tarjan per il 2 sabato

Question

L'algoritmo di Tarjan per 2-SAT è basato sulla verità:

.

Una formula a 2 cnf è soddisfatta se e solo se non vi è alcuna variabile che appartiene allo stesso componente fortemente collegato come negazione.

Ma non trovo alcun motivo per il diritto alla direzione sinistra. Come può l'inesistenza di tale garanzia variabile Soddisfazione del CNF?

Ho provato a seguire i passaggi dell'algoritmo, e sono stato bloccato qui:

.

Per ciascun componente nell'ordine topologico inversa, se le sue variabili non hanno già incarichi di verità, impostare tutti i letterali nel componente da verificare. Ciò causa anche tutti i letterali del componente complementare a false.

Non è possibile che la variabile sia già assegnata erroneamente? Quando continuiamo ad assegnare true dalla parte posteriore, e assegniamo il falso nel mezzo, ma il vero deve essere assegnato alla variabile successiva. In questo caso, la fattibilità si rompe.

Naturalmente questo tipo di custodia non succede mai perché l'algoritmo è giusto e molte persone usano bene questo algoritmo. Ma così tanti post lo dicono come le cose banale.

.
• Penso che il motivo per cui tali assegnazione è possibile è rilevante per la condizione simmetrica di inclinazione del grafico, poiché (x -> ~ x -> y -> ~ y) mai ha incarichi vere.

Answer 1

.

Una formula a 2 cnf è soddisfatta se e solo se non vi è alcuna variabile che appartiene allo stesso componente fortemente collegato come negazione.

Ma non trovo alcun motivo per il diritto alla direzione sinistra. Come può l'inesistenza di tale garanzia variabile Soddisfazione del CNF?

Pensa a un assegnazione variabile per qualche caso 2-SAT insoddisfacente. Ciò significa che una o più clausole devono rimanere insoddisfatte indipendentemente dall'assegnazione. Si modifica l'impostazione di una o più variabili per soddisfare quelle clausole, ma questo lascia inevitabilmente una nuova clausola o clausole insoddisfatte perché l'istanza è insoddisfacente. Il fallimento della tua modifica per soddisfare l'istanza implica che il valore di un altro valore della variabile deve cambiare. Ripeti la procedura ancora e ancora, cambiando altre variabili come richieste di implicazione, ma non riescono mai a soddisfare tutte le clausole. Alla fine, poiché il numero di variabili è finito, un errore implica che si modifica il valore di una variabile che hai già visitato ... E questa è la tua implicazione circolare da $ x $ < / span> a $ \ bar {x} $ Torna a $ x $ . Senza implicazione circolare alla fine raggiungerai la fine della catena di implicazione e avrai un compito soddisfacente. L'unico modo per non raggiungere la fine della catena è che la catena fosse circolare tra una variabile e la sua negazione.