[Math] How is HORNSAT equivalent to 2SAT

Question

I raise this question because I read Tim's question "Why are Hornsat, 3sat and 2sat not equivalent?".

Quoting him:

"… This new problem though is polynomial time equivalent to a certain instance of 2SAT(satisfiable iff the HORNSAT is). …"

How can I build the "certain instance of 2SAT"?

Can anybody give me pointers to papers that help writing the polynomial reduction from HORNSAT to 2SAT?

Answer 1

A little bit of research in wikipedia revealed this.

• HORNSAT is $P$-complete (see http://en.wikipedia.org/wiki/Horn-satisfiability).
• 2SAT is $NL$-complete (see http://en.wikipedia.org/wiki/2-satisfiability).
• It is known that $NL \subseteq P$, but unknown if $NL = P$ (see http://en.wikipedia.org/wiki/NL_%28complexity%29).

Thus 2SAT is reducible to HORNSAT and HORNSAT is reducible to 2SAT if and only if $NL=P$. Hence the existence of such a reducibility is an open question.