Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

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.

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.