Cómo funciona el algoritmo de Tarjan para el 2-SAT

Question

El algoritmo de Tarjan para 2-SAT se basa en la verdad:

Una fórmula 2-CNF es satisfactoria si y solo si no hay variable que pertenece al mismo componente fuertemente conectado como su negación.

Pero no encuentro ninguna razón para el derecho a la izquierda. ¿Cómo puede la inexistencia la satisfacción de la garantía de la variable de CNF?

Intenté seguir los pasos del algoritmo, y me quedé atrapado aquí:

Para cada componente en el orden topológico inverso, si sus variables aún no tienen asignaciones de verdad, establecen todos los literales en el componente para ser verdad. Esto también hace que todos los literales en el componente complementario se fijen en FALSO.

¿No es posible que la variable ya esté asignada incorrectamente? Cuando seguimos asignando VERDADERO desde la parte posterior, y asignamos la falsa en el medio, pero lo verdadero debe asignarse a la siguiente variable. En este caso, las interrupciones de factibilidad.

Por supuesto, este tipo de caso nunca sucede porque el algoritmo es correcto y muchas personas usan bien este algoritmo. Pero muchos post lo dicen como las cosas triviales.

• Creo que la razón por la que esas asignaciones es posible es relevante para la condición sespe-simética del gráfico, ya que (x -> ~ x -> y -> ~ y) nunca tiene tareas verdaderas.

Answer 1

Una fórmula 2-CNF es satisfactoria si y solo si no hay variable que pertenece al mismo componente fuertemente conectado como su negación.

Pero no encuentro ninguna razón para el derecho a la izquierda. ¿Cómo puede la inexistencia la satisfacción de la garantía de la variable de CNF?

Piense en una asignación variable para algún instancia de 2-SAT insatisfiable. Esto significa que una o más cláusulas deben permanecer insatisfechas, independientemente de la asignación. Cambia la configuración de una o más variables para satisfacer esas cláusulas, pero esto deja inevitablemente, una nueva cláusula o cláusulas insatisfechas porque la instancia es insatisfactoria. El fracaso de su cambio para satisfacer la instancia implica que el valor de otra variable debe cambiar. Repetió el procedimiento una y otra vez, cambiando otras variables como exigencias de implicación, pero nunca logran satisfacer todas las cláusulas. Eventualmente, debido a que la cantidad de variables es finita, una falla implica que cambia el valor de una variable que ya ha visitado ... y que es su implicación circular de $ x $ < / span> a $ \ bar {x} $ Volver a $ x $ . Sin una implicación circular, eventualmente llegará al final de la cadena de implicación y tendrá una tarea satisfactoria. La única forma de no alcanzar el final de la cadena es que la cadena sea circular entre una variable y su negación.