He estado leyendo un poco sobre la teoría de la complejidad recientemente, y me he encontrado con un pequeño obstáculo. El problema de satisfactibilidad de Horn es resoluble en tiempo lineal, pero el problema de satisfactibilidad booleana en general es NP-Difícil. Hasta aquí todo bien, entiendo eso.
Al parecer, la satisfactibilidad booleana es reducible a la satisfactibilidad de una expresión booleana en forma normal conjuntiva con 3 variables por cláusula. Sin embargo, este problema también es NP-Difícil. Eso también está bien para mí, ya que fue demostrado por alguien probablemente mucho más inteligente que yo.
Sin embargo, tengo problemas debido a la siguiente tautología:
(a∨b∨c)⟺((¬a∧¬b)⟹c)(a∨b∨c)⟺((¬a∧¬b)⟹c)
No es exactamente una cláusula de Horn, pero aún no he terminado.
Entonces, dado un problema 3SAT, aplicamos la tautología anterior.
Luego reemplazamos cada booleano negado ¬x¬x con una nueva variable xnxn
Esta es una instancia de HORNSAT, pero desafortunadamente no es equivalente al problema original. Sin embargo, este nuevo problema es polinomialmente equivalente a una cierta instancia de 2SAT (satisfactible si el HORNSAT lo es). Ahora, si por cada variable introducida xnxn, agregamos lo siguiente a nuestro problema 2SAT: (x∨xn)∧(¬x∨¬xn)(x∨xn)∧(¬x∨¬xn)
Entonces, ¿no debería esta instancia 2SAT ser equivalente al problema original de 3SAT? El número de variables se duplicó y tiene un factor lineal más de cláusulas.
Debo estar pasando por alto algo, ¿verdad? No logro ver el error por más que lo intento. ¿Alguien puede explicármelo?
EDIT: y un contraejemplo sería apreciado.