# 1- in -$k$ SAT to $k$-SAT reduction

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.

• Could you please define the terms you are using, and flesh out your question? – Aaron Sterling Aug 31 '11 at 0:39
• If $k$ is fixed, you don't even need extra variables in the reduction: For every clause $x_1\vee x_2 \vee \cdots \vee x_k$ you simply add $2^k-k-1$ clauses containing the same set of variables where some literals are negated. You add one such clause for each way to negate at least two of the literals. – Andreas Björklund Aug 31 '11 at 6:11
• Expand each 1-in-$k$ SAT clause $(X_1 \vee X_2 \cdots \vee X_k)$ to: $(X_1 \wedge -X_2 \cdots \wedge -X_k) \vee (-X_1 \wedge X_2 \cdots \wedge -X_k) \cdots \vee (-X_1 \wedge -X_2 \cdots \wedge X_k)$; convert to CNF distributing ORs over ANDs; finally convert to $k$-SAT – Marzio De Biasi Aug 31 '11 at 7:05
• Tks for your answers ! – Xavier Labouze Aug 31 '11 at 11:51

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.

1. following the definition, convert each $(X_1 \vee X_2 \vee \cdots \vee X_k)$ clause of the 1-in-$k$ SAT problem into $(X_1 \wedge -X_2 \wedge \cdots \wedge -X_k) \vee (-X_1 \wedge X_2 \wedge \cdots \wedge -X_k) \vee$ $\cdots \vee (-X_1 \wedge -X_2 \wedge \cdots \wedge X_k)$;
2. convert to CNF distributing ORs over ANDs;
3. convert the resulting CNF formula to $k$ SAT

For example $(x_1 \vee x_2 \vee -x_3)$ becomes:

1. $(x_1 \wedge -x_2 \wedge x_3) \vee (-x_1 \wedge x_2 \wedge x_3) \vee (-x_1 \wedge -x_2 \wedge -x_3)$;
2. $(x_1 \vee x_2 \vee -x_3) \wedge (-x_1 \vee -x_2) \wedge (-x_1 \vee x_3) \wedge (-x_2 \vee x_3)$
3. $(x_1 \vee x_2 \vee -x_3) \wedge (-x_1 \vee -x_2 \vee x4) \wedge (-x_1 \vee -x_2 \vee -x4)$ $\wedge (-x_1 \vee x_3 \vee x4) \wedge (-x_1 \vee x_3 \vee -x4)$ $\wedge (-x_2 \vee x_3 \vee x4) \wedge (-x_2 \vee x_3 \vee -x4)$

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)$