<p>Answer converted from comment.</p>

<p><strong>Definition:</strong> 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).</p>

<p>See for example <a href="http://en.wikipedia.org/wiki/One-in-three_3SAT" rel="nofollow">1-in-three SAT</a> on Wikipedia</p>

<p>The reduction from 1-in-$k$ SAT to $k$ SAT can be done easily.</p>

<ol>
<li>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)$; </li>
<li>convert to CNF distributing ORs over ANDs;</li>
<li>convert the resulting CNF formula to $k$ SAT</li>
</ol>

<p>For example $(x_1 \vee x_2 \vee -x_3)$ becomes:</p>

<ol>
<li>$(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)$;</li>
<li>$(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)$</li>
<li>$(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)$</li>
</ol>

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

CC BY-SA 3.0
2011-08-31T21:43:47.017Z
2011-09-01T06:50:57.177Z
2011-09-01T06:50:57.177Z
Marzio De Biasi
<p>The reduction from $k$-SAT to 1-in-$k$ SAT is known. </p>

<p>Would you help me to find a reduction from 1-in-$k$ SAT to $k$-SAT ? Thanks.</p>

CC BY-SA 3.0
2011-08-31T00:39:01.957Z
Could you please define the terms you are using, and flesh out your question?
Aaron Sterling
CC BY-SA 3.0
2011-08-31T06:11:49.757Z
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
CC BY-SA 3.0
2011-08-31T07:05:03.033Z
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
CC BY-SA 3.0
2011-08-31T11:51:30.740Z
Tks for your answers !
Xavier Labouze
<cc.complexity-theory><sat><reductions>
1- in -$k$ SAT to $k$-SAT reduction
Xavier Labouze
# 1- in -$k$ SAT to $k$-SAT reduction

(Asked by: username_0 on 2011-08-30)

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.

**Tags:** cc.complexity-theory, sat, reductions

> **Comments:**
> **username_1**: Could you please define the terms you are using, and flesh out your question?  
> **username_2**: 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.  
> **username_3**: 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  
> **username_0**: Tks for your answers !  

---

## 1 answers

### Answer by username_3 on 2011-08-31. Score: 4 | Accepted answer

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](http://en.wikipedia.org/wiki/One-in-three_3SAT) 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)$


---

