Comment fonctionne l'algorithme de Tarjan pour le 2-SAT

Question

L'algorithme de Tarjan pour 2-SAT est basé sur la vérité:

Une formule 2-CNF est satisfible si et uniquement s'il n'y a pas de variable appartenant au même composant fortement connecté que sa négation.

Mais je ne trouve aucune raison de la droite de gauche à gauche. Comment l'inexistence d'une telle variable garantit la satisfaction de CNF?

J'ai essayé de suivre les étapes de l'algorithme et j'étais coincé ici:

Pour chaque composant de l'ordre topologique inverse, si ses variables n'ont pas déjà d'affectations de vérité, définissez tous les littéraux dans le composant pour être vrai. Cela provoque également que tous les littéraux dans le composant complémentaire soient définis sur False.

n'est-il pas possible que la variable est déjà assignée à tort? Lorsque nous continuons à assigner de vrai à partir du dos et que nous assignons le faux au milieu, mais le vrai doit être attribué à la variable suivante. Dans ce cas, la faisabilité se casse.

Bien sûr, ce genre de cas n'arrivait jamais car l'algorithme a raison et de nombreuses personnes utilisent bien cet algorithme. Mais tant de poteau le dit comme des choses triviales.

• Je pense que la raison pour laquelle ces affectations sont possibles est pertinente pour la condition Skew-symétrique du graphique, car (x -> ~ x -> y -> ~ y) n'a jamais de véritables affectations.

Answer 1

une formule 2-CNF est satisfible si et uniquement s'il n'y a pas de variable appartenant au même composant fortement connecté que sa négation.

Mais je ne trouve aucune raison de la droite de gauche à gauche. Comment l'inexistence d'une telle variable garantit la satisfaction de CNF?

Pensez à une affectation variable pour une instance insatisfaite 2-SAT. Cela signifie qu'une ou plusieurs clauses doivent rester insatisfaites quelle que soit la cession. Vous modifiez la définition d'une ou plusieurs variables pour satisfaire ces clauses, mais cela laisse inévitablement une nouvelle clause ou des clauses insatisfaites car l'instance n'est pas satisfaite. L'échec de votre changement de satisfaire l'instance implique que la valeur d'une autre variable doit changer. Vous répétez la procédure encore et encore, changez d'autres variables comme des demandes d'implication, mais ne réussissez jamais à satisfaire toutes les clauses. Finalement, parce que le nombre de variables est fini, une défaillance implique que vous modifiez la valeur d'une variable que vous avez déjà visitée ... et c'est votre implication circulaire à partir de $ x $ < / Span> à $ \ bar {x} $ retour à $ x / span>. Sans une implication circulaire, vous allez finalement atteindre la fin de la chaîne d'implication et avoir une affectation satisfaisante. La seule façon de ne pas atteindre la fin de la chaîne est que la chaîne soit circulaire entre une variable et sa négation.