Satisfiability Problem

The satisfiability Problem is a widely studied problem in complexity theory. It serves as a base for polynomial time reduction.

Satisfiability (SAT) Problem

• Boolean formula f(a₁, a₂, …a_n) is satisfiable if there is a way to assign values to a variable of the formula such that the function evaluates to true. If this is the case, the function is satisfiable.
• On the other hand, if no such assignment is possible, the function is unsatisfiable.
• The expression (A ^ ¬B) is satisfiable for A = 1 and B = 0, but the expression (A ^ ¬A) is unsatisfiable.
• No known algorithm exists that solves the problem efficiently.

Example: f(x, y, z) = (x ∨ (y ∧ z) ) ∧ (x ∧ z)

X	y	z	x  ∨ (y ∧ z)	x ∧ z	f(x, y, z)
0	0	0	0	0	0
0	0	1	0	0	0
0	1	0	0	0	0
0	1	1	1	0	0
1	0	0	1	0	0
1	0	1	1	1	1
1	1	0	1	0	0
1	1	1	1	1	1

• The function is true for the combinations (x = 1, y = 0, z = 1) and (x = y = z = 1), hence it is satisfiable.
• Given the input sequence, it can be verified in linear time. But with n input n variables, there exist 2ⁿ instances. Testing each of them takes O(n.2ⁿ) time, which speaks SAT ∈ NP.

Circuit Satisfiability (CIRCUIT-SAT) Problem

A combinational circuit is a collection of AND, OR and NOT gates. Circuit satisfiability problem is to determine, given the combinational circuit, is it satisfiable?

• Given the assignment of the Boolean value for the input variable of the circuit, we can trace the output by assigning 0/1 to each input.
• If the final value of the circuit results in 1, the algorithm outputs “yes”, otherwise algorithm outputs “no”.
• This checking is done in polynomial time, more formally in the linear order of circuit size.

• If the circuit has k inputs, 2^k different assignments are possible. If the size of the circuit is polynomial in k, each assignment leads to a super-polynomial time algorithm.
• This proves that the polynomial time algorithm does not exist for circuit satisfiability problems and hence it is in NP.

3SAT Problem

3SAT problem is the problem of determining the satisfiability of a formula in conjunctive normal form (CNF) where each clause is limited to at most three literals. It is also known as 3CNFSAT or 3-Satisfiability problem

• 3SAT is a special case of SAT problems discussed earlier. 3SAT is an NP-complete problem.
• To show that 3SAT is NP-complete, we shall prove that any of the SAT instances can be reduced to an instance of 3SAT. By this we mean, we have to show how to convert the clauses which do not contain three literals into the one which does.
• Let us start with the clauses having 2 literals (x₁, x₂). We can introduce the new dummy literal u such that (x₁, x₂) is equivalent to (x₁, x₂, u) (x₁, x₂, u’).
• If clause has only one literal (x), we can recursively introduce literals u₁ and u₂ such that (x) corresponds to (x, u₁, u₂), (x, u₁, u₂‘), (x, u₁‘, u₂), (x, u₁‘, u₂‘).

If the clause has more than three literals (x₁, x₂, x₃, …, x_n), we can rewrite it as follows :

(x₁, x₂, u₁), (x₃, u₁‘, u₂), (x₄, u₂‘, u₃), … , (x_{n – 2}, u_n-4‘,u_{n – 3}), (x_{n – 1}, x_n, )

• One of the x_i must be true for the original clause to be true. To make a new arrangement equivalent to this, we shall set all u_i true till x_i encounters in the new arrangement.
• It can be seen that, if the original clause is satisfiable then its equivalent 3SAT representation is satisfiable too.
• Now, let us consider the countercase. For the original clause to be not satisfiable, all x_i must be false. To prove this, we will start with the counter-argument that some of them will be true in 3SAT representation.
• Assume that the last clause is true in 3SAT representation. As x_{n – 1} and x_n are false, u_{n – 3} must be false for (x_{n – 1}, x_n, u_n-3‘) clause to be true.
• For the second last clause to be true, u_{n – 4} must be false, as x_{n – 2} and x_n –3 are already false.
• This procedure will ensure that when we reach the first clause, all u_i must be false, and none of the x_i is true either. And hence it is proved that if the original clause is not satisfiable, then its equivalent 3SAT representation is also not satisfiable.
• This transformation is polynomial time transformation, this SAT ≤_p 3SAT, and hence 3SAT is an NP-complete problem.
• The 3-SAT problem can be generalized to the k-SAT problem. The k-SAT problem with k ≥ 3 is harder than 3-SAT and simpler than SAT problem and hence, k-SAT is also NP-complete.

---

Youtube Channel: CodeCrucks