3-Satisfiability Problem

computation

Definition

3-Satisfiability Problem

The 3-SAT problem is a specific form of the SAT where every clause consists of exactly 3 literals, where every literal is bound to a different variable.

Example: $(\neg x_1\vee x_2\vee x_3)\wedge (x_1\vee \neg x_2\vee x_3)\wedge (\neg x_1\vee \neg x_2\vee \neg x_3)$

Note: Sometimes, 3-SAT refers to the sub-problem of SAT where each clause has at most 3 literals.

Trivial Exponential Barrier

Problems in P can be solved in polynomial time

$$n^{O(1)},$$

where $n$ is the input size.

For NP-complete problems, no polynomial-time algorithm is known. Examples include SAT, 3-SAT, independent set, 3-colouring, and vertex cover.

The basic deterministic way to solve such problems is exhaustive search. For a Boolean formula with $n$ variables, try all truth assignments. This gives a running time of about

$$O(2^n\cdot n),$$

up to the cost of checking each assignment. For problems with three choices per variable or object, a similarly trivial search may give

$$O(3^n\cdot n).$$

These bounds are encoding-dependent because $n$ is the input size under the chosen encoding.

For 3-SAT, the trivial branching algorithm assigns one variable at a time. Each variable gives two branches: true and false. This produces a full binary search tree of depth $n$ and hence $2^n$ leaves.

The exact-algorithm question is whether one can break this trivial exponential barrier. For 3-SAT, one can do better than $O(2^n\cdot n)$ by branching more carefully than simply choosing an arbitrary unassigned variable.

Breaking the Exponential Barrier

The basic branching algorithm chooses one variable and creates two subinstances. For 3-SAT, one can branch on a whole clause instead.

Let $c$ be a clause. Since this is 3-SAT, $c$ contains at most three literals, and these literals use distinct variables.

• If $c$ has one literal, then it is a unit clause. Unit propagation fixes that literal.
• If $c$ has two literals over variables $x_i,x_j$, then there are only three satisfying assignments for $(x_i,x_j)$.
• If $c$ has three literals over variables $x_i,x_j,x_k$, then there are only seven satisfying assignments for $(x_i,x_j,x_k)$.

Thus one branching step removes $1$, $2$, or $3$ variables and creates at most $1$, $3$, or $7$ subinstances, respectively. The numbers $1,3,7$ come from excluding the assignments that do not satisfy the chosen clause:

• a unit clause has $1$ satisfying assignment;
• a 2-literal clause has $2^2-1=3$ satisfying assignments;
• a 3-literal clause has $2^3-1=7$ satisfying assignments.

Let $\alpha$ be the number of variables assigned in branches on clauses of size $3$, and let $\beta$ be the number of variables assigned in branches on clauses of size $2$.

A branch on a 3-literal clause assigns 3 variables and creates at most 7 subinstances. Thus $\alpha$ such assigned variables correspond to $\alpha /3$ branching steps, contributing a factor $7^{\alpha /3}$.

Variables counted by $\alpha$

If the algorithm branches on four 3-literal clauses, then it assigns $4\cdot 3=12$ variables through such branches. Hence $\alpha =12$, and these branches contribute

$$7^4=7^{\alpha /3}$$

leaves.

A branch on a 2-literal clause assigns 2 variables and creates at most 3 subinstances. Thus $\beta$ such assigned variables correspond to $\beta /2$ branching steps, contributing a factor $3^{\beta /2}$.

Variables counted by $\beta$

If the algorithm branches on five 2-literal clauses, then it assigns $5\cdot 2=10$ variables through such branches. Hence $\beta =10$, and these branches contribute

$$3^5=3^{\beta /2}$$

leaves.

Multiplying the two contributions, the number of leaves is at most

$$7^{\alpha /3}{3}^{\beta /2}.$$

Since $\alpha +\beta \le n$, this is bounded by

$$O\left(7^{n/3}\right)\subseteq O(1.913^n).$$

So 3-SAT can be solved exactly and deterministically in time

$$O(1.913^n),$$

where $n$ is the number of variables. This already breaks the trivial $O(2^n\cdot n)$ branching bound.

The O-star notation $O^{\ast }(f(n))$ suppresses polynomial factors. Thus $O^{\ast }(1.328^n)$ means $O(1.328^n{n}^d)$ for some constant $d$.