Reduce the
UNDIRECTED HAMILTONIAN CIRCUIT problem to the
SAT problem.
These problems are defined as follows:
- UNDIRECTED HAMILTONIAN CIRCUIT: given an undirected graph $G$, is
there a cycle that visits each node of $G$ exactly once? In other words, is it
possible to order the nodes of $G$ such that there is an edge between each $2$
contiguous nodes and an edge between the last and the first nodes?
More formally, this problem can be defined as the following set:
$\{ G=\langle V,E\rangle \mid V=\{n_1,\ldots,n_k\}\;\wedge\;\forall i\in\{1,\ldots,k\}: \{n_i,n_{(i\text{ mod }k)+1}\}\in E \}$
- 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: