The document SAT (Boolean Formula Satisfiability Problem) Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Theory of Computation.

All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

**Part IV. SAT (Boolean Formula Satisfiability Problem)**

**7 SAT****Satisfiability**

An example for a boolean formula is

(¬x_{1} ∪ x_{2}) ∩ (x_{1} ∪ ¬x_{2}) ∩ (¬x_{2} ∪ x_{3}) ∩ (¬x_{1 }∪ ¬x_{2} ∪ x_{3}).

This formula is in conjunctive normal form (CNF) (intersection of unions).

This boolean formula is satisfiable if there is some assignment of the values 0 and 1 to its variables that causes it to

evaluate to 1 (true).

If we put, x_{1 }= 0, x2 = 0, x_{3} = 1, we can see that the above formula evaluates to 1 (true).

This means above formula is satisfiable.

Consider the boolean formula,

(x_{1} ∪ x_{2}) ∩ (¬x_{1} ∪ ¬x_{2})

If we put x1 = 0, x_{2} = 0, this formula evaluates to 0. If we put x1 = 0, x_{2} = 1, this formula evaluates to 0. If we put

x_{1} = 1, x_{2 }= 0, this formula evaluates to 0. If we put x_{1} = 1, x_{2} = 1, this formula evaluates to 0. This means for any values assigned to the variables the above boolean formula always evaluate to 0 (false).

This means the formula is not satisfiable.

**SAT Problem**

SAT (Boolean Formula Satisfiability) problem is defined as:

Is there a set of values for the boolean variables that assigns the value 1 (true) to the boolean expression given in CNF?

**8 Cook’s Theorem**

Cook’s theorem states that

satisfiability of boolean formulas (SAT problem) is NP-Complete.

**SAT Problem is NP - Complete**

We know that a problem is in class NP-Complete if: it is in NP and it is NP Hard.

**Theorem:**

Satisfiability of boolean formulas is NP-Complete.

**Proof:****Step 1:** Prove that SAT problem is in class NP.

A boolean variable can have two possible values. Hence, for an n variable boolean expression in CNF, there are 2^{n} possible combinations of values of these variables.

If we want to check whether a boolean formula is satisfiable, we need to apply each combination to the formula until we get a 1 as the result of evaluation. In the worst case, we need to apply all the 2^{n }possible combinations.

Consider the formula, (¬x_{1} ∪ x_{2}) ∩ (x_{1} ∪ ¬x_{2}) ∩ (¬x_{2} ∪ x_{3}) ∩ (¬x_{1} ∪ ¬x_{2} ∪ x_{3}). There are 3 variables. Each variable can have two possible values, 0 or 1. There are 2^{3} combinations. So the time complexity of this problem is Θ(2n). (not polynomial time) If we are given a certificate containing a satisfiable assignment for a formula, then we can easily verify it in polynomial time.

For example, for the above formula, if we are given a certificate saying that if x^{1} = 0, x^{2} = 0, x^{3 }= 1, then just applying these values to the formula, we get,

(¬x_{1} ∪ x_{2}) ∩ (x_{1} ∪ ¬x_{2}) ∩ (¬x_{2} ∪ x_{3}) ∩ (¬x_{1} ∪ ¬x_{2} ∪ x_{3})

=(¬0 ∪ 0) ∩ (0 ∪ ¬0) ∩ (¬0 ∪ 1) ∩ (¬0 ∪ ¬0 ∪ 1)

=(1 ∪ 0) ∩ (0 ∪ 1) ∩ (1 ∪ 1) ∩ (1 ∪ 1 ∪ 1)

=1 ∩ 1 ∩ 1 ∩ 1=1

This can be done in linear time.

So the SAT problem is in class NP.

**Step 2: **Prove that SAT problem is NP-hard.

We know that a problem is NP-Hard, if every problem in NP can be reduced to this problem in polynomial time.

A lot of details are involved in this proof. [This proof is beyond the scope of this class].

[Refer the text book ’Introduction to the Theory of computation’ by Michael Sipser - Chapter 7- Theorem 7.37]

**3-CNF Satisfiability Problem (3-CNF-SAT)****3-CNF**

We know that a boolean formula is in conjunctive normal form(CNF) if it is expressed as an AND of clauses, each clause is the OR of one or more variables.

Then, a formula is in 3-conjunctive normal form (3-CNF) is each clause has exactly three distinct literals.

For example, the following boolean formula is in 3-CNF.

(x_{1} ∪ ¬x_{1} ∪ ¬x_{2}) ∩ (x_{3} ∪ x_{2} ∪ x_{4}) ∩ (¬x_{1} ∪ ¬x_{3} ∪ ¬x_{4}) ∩ (x_{2} ∪ x_{1} ∪ ¬_{x3})

The clauses in the above formula contain exactly 3 literals. The formula is in 3-CNF.**3-CNF Satisfiability Problem**

3-CNF-SAT problem is defined as:

Is there a set of values for the boolean variables that assigns the value 1 (true) to the boolean expression given in 3-CNF?

3-CNF Satisfiability Problem is NP-complete

We know that a problem is in class NP-Complete if: it is in NP and it is NP Hard.**Theorem:**

Satisfiability of boolean formulas in 3-CNF is NP-complete.

**Proof:****Step 1: **Prove that 3-CNF-SAT is in class NP.

A boolean variable can have two possible values. Hence, for an n variable boolean expression in CNF, there are 2^{n} possible combinations of values of these variables.

If we want to check whether a boolean formula is satisfiable, we need to apply each combination to the formula until we

get a 1 as the result of evaluation. In the worst case, we need to apply all the 2^{n} possible combinations.

Consider the 3-CNF formula, (x_{1} ∪ ¬x_{1} ∪ ¬x_{2}) ∩ (x_{3} ∪ x_{2} ∪ x_{4}) ∩ (¬x_{1} ∪ ¬x_{3} ∪ ¬x_{4}) ∩ (x_{2} ∪ x_{1} ∪ ¬_{x3}). There are 4 variables. Each variable can have two possible values, 0 or 1. There are 2^{4} combinations.So the time complexity of this problem is Θ(2^{n}). (not polynomial time) If we are given a certificate containing a satisfiable assignment for a formula, then we can easily verify it in polynomial time.**For example**, for the above formula, if we are given a certificate saying that if x^{1} = 0, x^{2} = 1, x^{3} = 0, x^{4} = 1, then

just applying these values to the formula, we get,

(x_{1} ∪ ¬x_{1} ∪ ¬x_{2}) ∩ (x_{3} ∪ x_{2} ∪ x_{4}) ∩ (¬x_{1} ∪ ¬x_{3} ∪ ¬x_{4}) ∩ (x_{2} ∪ x_{1} ∪ ¬_{x3})

=(0 ∪ ¬0 ∪ ¬1) ∩ (0 ∪ 1 ∪ 1) ∩ (¬0 ∪ ¬0 ∪ ¬1) ∩ (1 ∪ 0 ∪ ¬0)

=(0 ∪ 1 ∪ 0) ∩ (0 ∪ 1 ∪ 1) ∩ (1 ∪ 1 ∪ 0) ∩ (1 ∪ 0 ∪ 1)

=1 ∩ 1 ∩ 1 ∩ 1 ∩ 1=1

This can be done in linear time.

So the 3-CNF-SAT problem is in class NP.

**Step 2**: Prove that 3-CNF-SAT problem is NP-hard.

We know that a problem is NP-Hard, if every problem in NP can be reduced to this problem in polynomial time.

The approach we used is as follows:

In the previous section, we already proved that all NP problems can be reduced to SAT. Then, if we can reduce SAT to 3-CNF-SAT in polynomial time, we can say that 3-CNF-SAT is NP-hard.

We learned in the subject, ’logic design’ that any boolean formula can be expressed in CNF. Then, a boolean formula

in CNF can be rewritten in 3-CNF.

Consider a boolean formula as follows:

a ∪ b ∪ c ∪ d

This can be converted to 3-CNF as,

(a ∪ b ∪ x) ∩ (c ∪ d ∪ x)

Thus any boolean formula can be transformed to a 3-CNF boolean formula. This can be done using De Morgan’s laws.

That means SAT problem can be reduced to 3-CNF-SAT problem. That is, 3-CNF-SAT is NP-hard.

In step 1, we proved that 3-CNF-SAT is in NP.

In step 2, we proved that 3-CNF-SAT is NP-hard.

So, 3-CNF-SAT is an NP-complete problem.

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

18 videos|43 docs|39 tests