SAT (Boolean Formula Satisfiability Problem) | Theory of Computation - Computer Science Engineering (CSE) PDF Download

Part IV. SAT (Boolean Formula Satisfiability Problem)

7 SAT

Satisfiability
An example for a boolean formula is
(¬x₁ ∪ x₂) ∩ (x₁ ∪ ¬x₂) ∩ (¬x₂ ∪ x₃) ∩ (¬x₁ ∪ ¬x₂ ∪ x₃).
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₁ = 0, x2 = 0, x₃ = 1, we can see that the above formula evaluates to 1 (true).
This means above formula is satisfiable.

Consider the boolean formula,
(x₁ ∪ x₂) ∩ (¬x₁ ∪ ¬x₂)
If we put x1 = 0, x₂ = 0, this formula evaluates to 0. If we put x1 = 0, x₂ = 1, this formula evaluates to 0. If we put
x₁ = 1, x₂ = 0, this formula evaluates to 0. If we put x₁ = 1, x₂ = 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ⁿ 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ⁿ possible combinations.
Consider the formula, (¬x₁ ∪ x₂) ∩ (x₁ ∪ ¬x₂) ∩ (¬x₂ ∪ x₃) ∩ (¬x₁ ∪ ¬x₂ ∪ x₃). There are 3 variables. Each variable can have two possible values, 0 or 1. There are 2³ 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¹ = 0, x² = 0, x³ = 1, then just applying these values to the formula, we get,
(¬x₁ ∪ x₂) ∩ (x₁ ∪ ¬x₂) ∩ (¬x₂ ∪ x₃) ∩ (¬x₁ ∪ ¬x₂ ∪ x₃)
=(¬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₁ ∪ ¬x₁ ∪ ¬x₂) ∩ (x₃ ∪ x₂ ∪ x₄) ∩ (¬x₁ ∪ ¬x₃ ∪ ¬x₄) ∩ (x₂ ∪ x₁ ∪ ¬_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ⁿ 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ⁿ possible combinations.
Consider the 3-CNF formula, (x₁ ∪ ¬x₁ ∪ ¬x₂) ∩ (x₃ ∪ x₂ ∪ x₄) ∩ (¬x₁ ∪ ¬x₃ ∪ ¬x₄) ∩ (x₂ ∪ x₁ ∪ ¬_x3). There are 4 variables. Each variable can have two possible values, 0 or 1. There are 2⁴ combinations.So the time complexity of this problem is Θ(2ⁿ). (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¹ = 0, x² = 1, x³ = 0, x⁴ = 1, then
just applying these values to the formula, we get,

(x₁ ∪ ¬x₁ ∪ ¬x₂) ∩ (x₃ ∪ x₂ ∪ x₄) ∩ (¬x₁ ∪ ¬x₃ ∪ ¬x₄) ∩ (x₂ ∪ x₁ ∪ ¬_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.