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.