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 NPComplete.
SAT Problem is NP  Complete
We know that a problem is in class NPComplete if: it is in NP and it is NP Hard.
Theorem:
Satisfiability of boolean formulas is NPComplete.
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 NPhard.
We know that a problem is NPHard, 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]
3CNF Satisfiability Problem (3CNFSAT)
3CNF
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 3conjunctive normal form (3CNF) is each clause has exactly three distinct literals.
For example, the following boolean formula is in 3CNF.
(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 3CNF.
3CNF Satisfiability Problem
3CNFSAT 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 3CNF?
3CNF Satisfiability Problem is NPcomplete
We know that a problem is in class NPComplete if: it is in NP and it is NP Hard.
Theorem:
Satisfiability of boolean formulas in 3CNF is NPcomplete.
Proof:
Step 1: Prove that 3CNFSAT 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 3CNF 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 3CNFSAT problem is in class NP.
Step 2: Prove that 3CNFSAT problem is NPhard.
We know that a problem is NPHard, 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 3CNFSAT in polynomial time, we can say that 3CNFSAT is NPhard.
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 3CNF.
Consider a boolean formula as follows:
a ∪ b ∪ c ∪ d
This can be converted to 3CNF as,
(a ∪ b ∪ x) ∩ (c ∪ d ∪ x)
Thus any boolean formula can be transformed to a 3CNF boolean formula. This can be done using De Morgan’s laws.
That means SAT problem can be reduced to 3CNFSAT problem. That is, 3CNFSAT is NPhard.
In step 1, we proved that 3CNFSAT is in NP.
In step 2, we proved that 3CNFSAT is NPhard.
So, 3CNFSAT is an NPcomplete problem.
18 videos56 docs44 tests

1. What is the SAT problem in computer science engineering? 
2. How is the SAT problem relevant to computer science engineering? 
3. What is the complexity of solving the SAT problem in computer science engineering? 
4. What are some common techniques used to solve the SAT problem? 
5. What are the practical implications of solving the SAT problem in computer science engineering? 
18 videos56 docs44 tests


Explore Courses for Computer Science Engineering (CSE) exam
