Statement

Proof

We already know 3-SAT is in NP, as shown in k-SAT is in NP.

So, we need to demonstrate that 3-SAT is NP-hard. This will be done by establishing a many-one reduction to the SAT problem, which is NP-complete (see SAT is NP-complete). Specifically, we will show the following:

A SAT problem instance can be transformed into a 3-SAT problem instance in polynomial time. The solution to the 3-SAT problem can be used to solve the SAT problem. A solution for the 3-SAT problem exists if and only if a solution for the SAT problem exists. Let $f$ be a CNF formula using $n$ variables with $m$ clauses. Our goal is to construct $f'$, a CNF formula that falls under 3-SAT.

For each clause $C$ in $f$, we proceed as follows:

If the clause contains 3 or fewer literals, we keep the formula unchanged, letting $C' = C$. Otherwise, we apply clause reduction to obtain $C'$. Then, we add $C'$ to $f'$. Since every clause in $f'$ has at most 3 literals, $f'$ belongs to 3-SAT.

The clause reduction process takes $O(n)$ time, as each clause can be at most $n$ literals long. Applying clause reduction up to $m$ times, the reduction is done in $O(nm)$, a polynomial time.

We then solve $f'$ using 3-SAT. If no solution is found, we conclude the same for the original; otherwise, we use the solution for the original $n$ variables. This step takes $O(1)$ time.

From Claim 1, each clause $C$ of $f$ is satisfiable if and only if its clause reduction $C'$ is satisfiable. Therefore, since $f'$ consists of clause reductions of $f$’s clauses, $f'$ is satisfiable if and only if $f$ is.

Hence, $f'$ has a solution if and only if $f$ does, establishing a valid reduction of the SAT problem to 3-SAT.

This proves that 3-SAT is NP-complete, as initially stated.

Clause reduction

Claim 1

Proof of claim 1

$\Rightarrow$

Suppose we have some assignment to the variables $n$ variables such that $C$ is satisfied. Then we know at least one literal $l_a$ is true.

To make a satisfying assignment for $C'$ first keep the assignment the same for the original $n$ variables and

• set $y_i$ to be true for all $i \leq a - 2$, and
• set $y_i$ to be false for all $i \geq a - 1$.

For the first $a - 2$ clauses (in the case of $a = k$ the first $k-3$ clauses) in $C'$ they all contain $y_i$ for some $i \leq a - 2$. Therefore they are satisfied in this allocation as $y_i$ is true for all $i \leq a - 2$.

For the $a - 1$‘th clause (in the case of $a = 1$ the first clause and in the case of $a = k$ the $k-2$‘th clause) it contains $l_a$. Therefore this clause is satisfied.

For the $a$‘th clause and above (in the case of $a = 1$ the 2’nd clause and above) it contains $\overline{y_i}$ for some $i \geq a - 1$. Therefore they are satisfied in this allocation as $y_i$ is false for $i \geq a - 1$.

This makes $C'$ satisfiable.

$\Leftarrow$

Suppose instead $C'$ is satisfiable. Therefore we have some assignment to the original $n$ variables and an assignment to $y_i$ for $1 \leq i \leq k-3$ such that $C'$ is satisfied - so every clause in $C'$ is true.

There are 3 cases for $y_i$:

• $y_1$ is false,
• $y_{k-3}$ is true, or
• There exists and $1 \leq i \leq k-2$ such that $y_i$ is true and $y_{i+1}$ is false.

(Note if $y_1$ is true and $y_{k-3}$ is false then there must be $i$ which $y_i$ goes from being true to $y_{i+1}$ being false.)

Note in all these cases as $C'$ is satisfied there is an $l_i$ that is true.

• If $y_1$ is false either $l_1$ or $l_2$ is true.
• If $y_{k-3}$ is true either $l_{k-1}$ or $l_k$ is true.
• If $y_i$ is true and $y_{i+1}$ is false then $l_{i+2}$ is true.

Therefore as $l_i$ is true, assignment to the original $n$ variables satisfies $C$.