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:
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 con una nueva variable
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 , agregamos lo siguiente a nuestro problema 2SAT:
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.