# How is HORNSAT equivalent to 2SAT?

I rises 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"?

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

-

## 1 Answer

A little bit of research in wikipedia revealed this.

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.

-
So, I think I have misunderstood the meaning of the word "equivalence" that occurs in the quote of my question. After your answer, I think I can correctly interpret the meaning of the final posts between Tim and Stefan, relative to "Why are Hornsat, 3sat and 2sat not equivalent?". Many thanks. Luca –  rover Nov 2 '11 at 16:19
@rover There was the issue of producing a reduction which preserves witnesses. There is a trivial reduction, but it doesn't preserve witnesses so it isn't useful for solving hornsat. I would also like to point out that NL=(!=)P doesn't concern polynomial time reductions since we wouldn't gain anything by that. 2SAT is linear time solvable, so we need an at most logspace reduction for it to mean anything useful. –  Tim Seguine Dec 10 '11 at 20:11