3-SAT to 3-Horn SAT (Karp Reduction)

Definition

3-SAT to 3-Horn SAT

The identity map is a polynomial-time many-one reduction

$$3\text{-}\mathrm{SAT}{\le }_m^{p}3\text{-}\mathrm{HORN}\mathrm{SAT}$$

from 3-SAT to 3-Horn SAT, where the latter allows at most three positive literals per clause and arbitrarily many negative literals.

Construction

Keep the formula, relax the restriction

Given a 3-SAT formula $F$, output $f(F)=F$. Every clause $C$ satisfies

$$\underset{\text{target restriction}}{\underbrace{\#\{\text{positive literals in }C\}}}\le \underset{\text{source restriction}}{\underbrace{|C|}}\le 3.$$

Thus the unchanged formula is a valid target instance. The two problems ask the same question about that formula.

No variables, clauses or gadgets are added. The target permits more formulas, but that does not change satisfiability of the formula we output.

Correctness and running time

Identity preserves satisfiability

Forward

If $F$ is satisfiable as a 3-SAT instance, its satisfying assignment also satisfies the identical target formula $f(F)=F$.

Backward

If the target formula is satisfiable, the same assignment satisfies the original formula, since none of its clauses changed.

Polynomial construction

Copying the formula takes $O(|F|)$ time, where $|F|$ is its encoding length. Checking the source clause-size restriction is also polynomial.

NP-completeness

3-Horn SAT is NP-complete

3-Horn SAT is NP-complete.

Proof

The reduction establishes NP-hardness. For membership in NP, a certificate assigns one truth value to every variable. Checking that each clause has a true literal takes time linear in the formula length; checking the input restriction is also polynomial. This is a direct verification argument, not a claim that arbitrary subsets of NP languages belong to NP.