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?


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.

| cite | improve this answer | |
  • $\begingroup$ 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 $\endgroup$ – rover Nov 2 '11 at 16:19
  • $\begingroup$ @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. $\endgroup$ – Tim Seguine Dec 10 '11 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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