Definiciones:
SAT es el problema "Dado un enunciado de lógica proposicional, ¿tiene el enunciado una asignación de sus variables que resulte en que el enunciado sea verdadero?".
3-SAT es un problema SAT, escrito como cláusulas con 3 variables o menos. Por ejemplo ((A or B or C) and (not B or not C)) tiene 2 cláusulas. A , B y C son variables booleanas; " or " y " and "son los operadores lógicos estándar. Este problema tiene al menos una solución (A, B, C) = (true, false, true) .
2-SAT es un problema SAT, escrito como cláusulas con 2 variables o menos.
Podemos reducir 2-SAT al problema de encontrar un ciclo en un grafo dirigido : Podemos crear un vértice para cada variable (y su negación). Escribimos cada cláusula ((A) or (B)) en forma de implicación: ((A) or (B)) <=> ((not (not A)) or (B)) <=> ((not A) implies (B)) . Añadimos una arista dirigida para cada cláusula "implica". El problema 2-SAT se satisface si y sólo si para todas las variables X , vértices (X) y (not X) no están contenidos en un ciclo. (Equivalentemente, hay un camino desde (X) a (not X) y un camino desde (not X) a (X) si y sólo si hay una contradicción - es decir, si el problema 2-SAT no se satisface).
¿Se puede reducir una cláusula 3-SAT "directamente" (definida en [3]) a un problema 2-SAT?
[1] 2-SAT es equivalente a "para algún X, ¿contiene el gráfico de implicación ambos caminos desde (X) a (not X) y de (not X) a (X) ?
[2] En otras palabras, un problema 2-SAT se satisface si y sólo si 2 vértices de su grafo de implicación se contradicen (están en el mismo ciclo).
Entonces, ¿cómo puede haber una reducción "directa" de una cláusula 3-SAT a 2-SAT?
[3] Si hay una reducción "directa" de una cláusula 3-SAT a 2-SAT, entonces, para cada cláusula D = (A or B or C) existirán 3 vértices A , B , C en el grafo de implicación 2-SAT tal que la cláusula D se cumple si y sólo si (not ((not A) and (not B) and (not C))) (lo que falsea la cláusula).
[4] Hay 3 variables que intervienen allí ([3]) en la satisfacción.
[5] Un problema 2-SAT se satisface, o no, en función de 2 vértices ([2]).
[6] No se puede codificar "insatisface si y sólo si 3 variables se contradicen" en aristas dirigidas ("directamente"). (Un problema 2-SAT podría tener múltiples pares de vértices contradictorios; cada contradicción corresponde a un par de vértices. No se pueden "meter" 3 "en" un par).
[7] Según [6], si una cláusula 3-SAT se puede reducir "directamente" a 2-SAT, entonces, no debe ser uno-a-uno con las variables.
Por lo tanto, una cláusula 3-SAT no puede reducirse "directamente" a 2-SAT.
