# How is HORNSAT equivalent to 2SAT?

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?

-

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.