4
$\begingroup$

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?

1 Answers 1

4

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.

  • 0
    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?"](http://math.stackexchange.com/questions/66630/why-are-hornsat-3sat-and-2sat-not-equivalent). Many thanks. Luca2011-11-02
  • 0
    @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.2011-12-10