¿Cómo se HORNSAT equivalente a 2SAT?

Question

Planteo esta pregunta porque he leído Tim's la pregunta "¿por Qué Hornsat, 3sat y 2sat no es equivalente?".

Citando a él:

"... Este nuevo problema, aunque es el polinomio de tiempo equivalente a una instancia determinada de 2SAT(conste que si el HORNSAT es). ..."

¿Cómo puedo construir el "cierta instancia de 2SAT"?

¿Alguien puede darme punteros a los papeles que le ayuden a escribir el polinomio de reducción de HORNSAT a 2SAT?

Answer 1

Un poco de investigación en wikipedia reveló este.

• HORNSAT es $P$- (véase http://en.wikipedia.org/wiki/Horn-satisfiability).
• 2SAT es $NL$- (véase http://en.wikipedia.org/wiki/2-satisfiability).
• Se sabe que $NL \subseteq P$, pero se desconoce si $NL = P$ (ver http://en.wikipedia.org/wiki/NL_%28complexity%29).

Por lo tanto 2SAT es reducible a HORNSAT y HORNSAT es reducible a 2SAT si y sólo si $NL=P$. De ahí la existencia de un reducibilidad es una pregunta abierta.