Alex's Notes

Week 10 - NP-completeness

1 min read

Week 10 - NP-completeness

We are going to assume the following.

Statement

Cook-Levin Theorem (1971)

The Satisfiability problem is NP-complete.

Link to original

k-SAT

We are going to show that the k-SAT problem is NP-Complete for .

Statement

k-SAT Problem

Given a boolean function in CNF with variables and clauses of size at most . Is there a true/false assignment to the variables that satisfies . If yes then output it, otherwise say no.

Link to original

To do this we will show 3-SAT is NP-complete which as 3-SAT is a subproblem to k-SAT for this will prove all we need to.

We need to do the following to show this:

k-SAT is in NP

k-SAT is in NP

Statement

Lemma

k-SAT is in NP

Proof

k-SAT is in the correct form for a search problem. It either outputs an assignment that satisfies the formula or it says no such assignment exists.

To check an assignment we have to check each clause, with each clause we check of the variables which takes at most time - polynomial in the input size.

Therefore k-SAT is in NP.

Link to original

3-SAT is NP-Complete

3-SAT is NP-complete

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 .

Link to original

Though this has shown us even more than just 3-SAT.

k-SAT is NP-complete for k greater than or equal to 3

Statement

Lemma

k-SAT is NP-complete for

Proof

Note that k-SAT is in NP.

Separately we have shown 3-SAT is NP-complete. In this proof we showed a reduction of the SAT problem to 3-SAT. The clause reduction in this takes a SAT problem and reduces it to a problem in 3-SAT. The same reduction can we used to reduce the SAT problem to k-SAT for all , as a CNF with at most terms has at most terms for .

Therefore k-SAT is NP-hard and in NP so is NP-complete.

Link to original

Practice problems

From Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.

8.3 Stingy SAT

8.8 Exact 4-SAT

Graph View

Backlinks