1
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Could you please define the terms you are using, and flesh out your question? $\endgroup$ – Aaron Sterling Aug 31 '11 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$ – Andreas Björklund Aug 31 '11 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$ – Marzio De Biasi Aug 31 '11 at 7:05
  • $\begingroup$ Tks for your answers ! $\endgroup$ – Xavier Labouze Aug 31 '11 at 11:51
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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