Reduction: SAT → 3SAT

Any clause with more than three literals

(a_1 \vee a_2 \vee \cdots \vee a_k)

Can be reduced to

(a_1 \vee a_2 \vee y_1)(\bar{y}_1 \vee a_3 \vee y_2) (\bar{y}_2 \vee a_4 \vee y_3) \cdots (\bar{y}_{k-3} \vee a_{k-1} \vee a_k)

Where the $y_i$ are new variables

The conversion from $I$ to $I’$ is polynomial time.

$I’$ is not logically equivalent to $I$ , but it is equivalent in terms of satisfiability

\biggl\{\begin{split} (a_1 \vee a_2 \vee \cdots a_k) \\ \text{is satisfied} \end{split}\biggr\} \equiv \Biggl\{\begin{split} \text{there is a setting of the $y_i$ for which} \\ (a_1 \vee a_2 \vee y_1)(\bar{y}_1 \vee a_3 \vee y_2) \cdots (\bar{y}_{k-3} \vee a_{k-1} \vee a_k) \\ \text{are satisfied} \end{split}\Biggr\}

Suppose clauses on the right are satisfied, then at least one of the literals $a_1, \dots, a_k$ must be true - otherwise $y_1$ would have to be true, which would force $y_2$ to be true, and so on, eventually falsifying the last clause.

Conversely, if $(a_1 \vee a_2 \vee \cdots \vee a_k)$ is satisfied, then some $a_i$ must be true. Set $y_1, \dots, y_{i-2}$ to true and set the rest to $false$ . This made the clauses on the right to be satisfied.

We can further reduce 3SAT to a “constrained version” such that no variable appears in more than three clauses.

Suppose in the 3SAT instance variable $x$ appears in $k>3$ clauses then replace its first appearance by $x_1$ , its second appearance by $x_2$ and so on.

Also add the clauses

(\bar{x}_1 \vee x_2)(\bar{x}_2 \vee x_3) \cdots (\bar{x}_k \vee x_1)