Reduce the
3-COLORABILITY problem to the
SAT problem.
These problems are defined as follows:
- 3-COLORABILITY: given an undirected graph $G$, is $G$ $3$-colorable?
In other words, is there a mapping $M$ from the nodes of $G$ to $\{1,2,3\}$
satisfying $M(u)\neq M(v)$ for each edge $\{u,v\}$ of $G$?
More formally, this problem can be defined as the following set:
$\{ G=\langle V,E\rangle \mid \exists M:V\to\{1,2,3\}\text{ total}: \forall \{u,v\}\in E: M(u)\neq M(v) \}$
- SAT: given a boolean formula $F$ in conjunctive normal form, is $F$
satisfiable?
More formally, this problem can be defined as the following set:
$\{ F=C_1\wedge\ldots\wedge C_n \mid F\text{ satisfiable} \}$
The input and output of the reduction conform to the following data types: