<p>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.</p>

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

<p>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.</p>

CC BY-SA 2.5
2011-01-06T02:06:59.110Z
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
CC BY-SA 2.5
2011-01-06T03:12:35.060Z
You solve the SAT instance and then output a satisfiable or unsatisfiable HORN-SAT depending on the answer.
Mark Reitblatt
CC BY-SA 2.5
2011-01-05T23:02:51.287Z
2011-01-05T23:02:51.287Z
Mark Reitblatt
<p>See <a href="https://cstheory.stackexchange.com/questions/200/translating-sat-to-hornsat">Translating SAT to HornSAT</a> </p>

<p>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? </p>

<cc.complexity-theory>
Translating HORNSAT to SAT, revisited
Craig Feinstein
# Translating HORNSAT to SAT, revisited

(Asked by: username_0 on 2011-01-05)

See [Translating SAT to HornSAT](https://cstheory.stackexchange.com/questions/200/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?

**Tags:** cc.complexity-theory


---

## 1 answers

### Answer by username_1 on 2011-01-05. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: You solve the SAT instance and then output a satisfiable or unsatisfiable HORN-SAT depending on the answer.  

---

