The reduction from $k$-SAT to 1-in-$k$ SAT is known.
Would you help me to find a reduction from 1-in-$k$ SAT to $k$-SAT ? Thanks.
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.Sign up to join this community
Answer converted from comment.
Definition: 1-in-$k$ SAT is a $k$-SAT problem with the tighter condition that - given a truth assignment to the variables - each clause must contain exactly one true literal (and thus $k$-1 false literals).
See for example 1-in-three SAT on Wikipedia
The reduction from 1-in-$k$ SAT to $k$ SAT can be done easily.
For example $(x_1 \vee x_2 \vee -x_3)$ becomes:
Note: at step 3, if you allow repeated variables in a clause, then there is non need for the extra variable and the final $k$ SAT formula of the example can be: $(x_1 \vee x_2 \vee -x_3) \wedge (-x_1 \vee -x_2 \vee -x2)$ $\wedge (-x_1 \vee x_3 \vee x3)$ $\wedge (-x_2 \vee x_3 \vee x3)$