Alex's Notes

3-SAT is NP-complete

4 min read

Statement

Lemma

3-SAT is NP-complete.

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 be a CNF formula using variables with clauses. Our goal is to construct , a CNF formula that falls under 3-SAT.

For each clause in , we proceed as follows:

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

The clause reduction process takes time, as each clause can be at most literals long. Applying clause reduction up to times, the reduction is done in , a polynomial time.

We then solve using 3-SAT. If no solution is found, we conclude the same for the original; otherwise, we use the solution for the original variables. This step takes time.

From Claim 1, each clause of is satisfiable if and only if its clause reduction is satisfiable. Therefore, since consists of clause reductions of ‘s clauses, is satisfiable if and only if is.

Hence, has a solution if and only if 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

Clause reduction

Given a clause with literals in our variables. We define the reduction where are some new variables.

Claim 1

Claim 1

A clause is satisfiable if and only if it’s clause reduction is satisfiable.

Proof of claim 1

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

To make a satisfying assignment for first keep the assignment the same for the original variables and

  • set to be true for all , and
  • set to be false for all .

For the first clauses (in the case of the first clauses) in they all contain for some . Therefore they are satisfied in this allocation as is true for all .

For the ‘th clause (in the case of the first clause and in the case of the ‘th clause) it contains . Therefore this clause is satisfied.

For the ‘th clause and above (in the case of the 2’nd clause and above) it contains for some . Therefore they are satisfied in this allocation as is false for .

This makes satisfiable.

Suppose instead is satisfiable. Therefore we have some assignment to the original variables and an assignment to for such that is satisfied - so every clause in is true.

There are 3 cases for :

  • is false,
  • is true, or
  • There exists and such that is true and is false.

(Note if is true and is false then there must be which goes from being true to being false.)

Note in all these cases as is satisfied there is an that is true.

  • If is false either or is true.
  • If is true either or is true.
  • If is true and is false then is true.

Therefore as is true, assignment to the original variables satisfies .

Graph View

Backlinks