7
$\begingroup$

See Translating SAT to HornSAT

It says in that post that it is impossible to translate SAT into HORNSAT. But it is known that HORNSAT is P-complete, so any language in P can be translated into HORNSAT. Then if it is impossible to translate SAT, which is in NP, into HORNSAT, then wouldn't this imply that P is not NP? What am I missing?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

That question was about a translation from an arbitrary instance of SAT to a HORN-SAT instance with the exact same satisfying assignments. The translation property needed for P$\neq$NP is just equisatisfiability, not equality of assignments. That is, it simply requires them both to be satisfiable, or unsatisfiable. If satisfiable, they may be satisfied by different assignments.

For example: $a \wedge \neg b$ and $\neg a \wedge b$ are equisatisfiable (they are both satisfiable), but they have different satisfying assignments.

The answer was that there can not be a satisfying assignment preserving translation, but this doesn't tell us whether there is a polynomial time satisfiability preserving translation.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you. I notice in that post that one of the comments mentions a trivial reduction from SAT to HORNSAT, without taking into account efficiency (not a polynomial reduction). What is this reduction? $\endgroup$
    – Craig Feinstein
    Jan 6, 2011 at 2:06
  • 1
    $\begingroup$ You solve the SAT instance and then output a satisfiable or unsatisfiable HORN-SAT depending on the answer. $\endgroup$
    – Mark Reitblatt
    Jan 6, 2011 at 3:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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