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=⟨V,E⟩∣V={n1,…,nk}∧∀i∈{1,…,k}:{ni,n(i mod k)+1}∈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=C1∧…∧Cn∣F satisfiable}
The input and output of the reduction conform to the following data types: