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.

  • 4
    $\begingroup$ Could you please define the terms you are using, and flesh out your question? $\endgroup$ Aug 31, 2011 at 0:39
  • $\begingroup$ 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. $\endgroup$ Aug 31, 2011 at 6:11
  • $\begingroup$ 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 $\endgroup$ Aug 31, 2011 at 7:05
  • $\begingroup$ Tks for your answers ! $\endgroup$ Aug 31, 2011 at 11:51

1 Answer 1


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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.