7

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?

Community
  • 1
Craig Feinstein
  • 515
  • 6
  • 14

1 Answers1

8

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.

Mark Reitblatt
  • 1,690
  • 15
  • 20
  • 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? – Craig Feinstein Jan 06 '11 at 02:06
  • 1
    You solve the SAT instance and then output a satisfiable or unsatisfiable HORN-SAT depending on the answer. – Mark Reitblatt Jan 06 '11 at 03:12