5
$\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
    @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