Reduce the
3-SAT problem to the
1-in-3-SAT problem.
These problems are defined as follows:
- 3-SAT: given a boolean formula $F$ in conjunctive normal form where
each clause has $3$ literals, 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}\;\wedge\;\forall i\in\{1,\ldots,n\}: |C_i|=3 \}$
- 1-in-3-SAT: given a boolean formula $F$ in conjunctive normal form
where each clause has $3$ literals, is there a truth assignment to the
variables of $F$ such that each clause of $F$ has exactly one true literal?
More formally, this problem can be defined as the following set:
$\{ F=C_1\wedge\ldots\wedge C_n \mid F\text{ satisfiable with exactly one true literal per clause}\;\wedge\;\forall i\in\{1,\ldots,n\}: |C_i|=3 \}$
The input and output of the reduction conform to the following data types: