How to show ExactOneSAT is NP-Complete?

Question

$\text{ExactOneSAT}= \{\phi\;|\;\phi\; \text{is a boolean formula}$ $\text{ such that it has a satisfying assignment with only one true literal per clause} \}$

I am trying to reduce 3SAT to this problem but can't find a way. I tried taking a small example $\phi=(x_1 \vee x_2) \wedge (\overline{x_1} \vee x_2 ) $. In this example the formula can only be satisfied only when both $x_1,x_2$ are True. How do I reduce such a case of 3SAT to ExactOneSAT ?
This is an exercise from Sanjeev Arora and Barak Boaz : A modern approach to complexity, but not a homework exercise.

Answer 1

We can reduce 3SAT to ExactOneSAT (3SAT $\leq_P$ ExactOneSAT) as follows. Replace each clause $C_m$ by $(z_{m,1} \lor z_{m,2} \lor z_{m,3})$ and ensure that if $C_m$ is, say, $(v_i \lor \overline{v_j} \lor v_k)$ then $(\neg v_i \Rightarrow \neg z_{m,1})$, $(\neg \overline{v_j} \Rightarrow \neg z_{m,2})$ and $(\neg v_k \Rightarrow \neg z_{m,3})$. Thus, for example, if $v_i$ is true then $z_{m,1}$ can be true or false, but if $v_i$ is false then $z_{m,1}$ must be false.

Thus replace $(X_{m}^1 \lor X_{m}^2 \lor X_{m}^3)$ in clause $C_m$ by
$$(z_{m,1} \lor z_{m,2} \lor z_{m,3}) \land (\neg X_{m}^1 \lor y_{m,1} \lor z_{m,1}) \land ( \neg X_{m}^2 \lor y_{m,2} \lor z_{m,2}) \land ( \neg X_{m}^3 \lor y_{m,3} \lor z_{m,3})$$
where $X^1_m, X^2_m, X^3_m$ are the three literals in the clause $C_m$. Note that $X$'s are literals in the clauses and can have negations, whereas $y$'s and $z$'s are variables.

If $\phi'$ is the modified boolean CNF, then this will give us $\phi \in$ 3SAT iff $\phi' \in $ ExactOneSAT. This along with the fact that above transformation is polynomial-time gives us a proof of NP-completeness.

Let us see how $\phi \in 3SAT \Rightarrow \phi' \in$ ExactOneSAT.

Assume we have a satisfying assignment for $\phi$.

For example, say $X_m^1$ is true and $X_m^2$ and $X_m^3$ are false. Then we can make following assignments:

$y_{m,1}$ = False, $z_{m,1}$ = True
$y_{m,2}$ = False, $z_{m,2}$ = False
$y_{m,3}$ = False, $z_{m,3}$ = False

For example, say $X_m^1$ and $X_m^2$ are true and $X_m^3$ is false. Then we can make following assignments:

$y_{m,1}$ = False, $z_{m,1}$ = True
$y_{m,2}$ = True, $z_{m,2}$ = False
$y_{m,3}$ = False, $z_{m,3}$ = False

For example, say all $X_m^1$, $X_m^2$ and $X_m^3$ are true. Then we can make following assignments:

$y_{m,1}$ = False, $z_{m,1}$ = True
$y_{m,2}$ = True, $z_{m,2}$ = False
$y_{m,3}$ = True, $z_{m,3}$ = False

So we can see that we can find a satisfying assignment for $\phi'$ where only one literal is true in every clause.

Let us now see how $\phi' \in$ ExactOneSAT $\Rightarrow \phi \in $ 3SAT

Assume we have a satisfying assignment for $\phi'$ where exactly one literal is true in every clause.

Let us say $z_{m,1}$ is true and $z_{m,2}$ and $z_{m,3}$ are false. Then definitely $X_m^1$ in the second clause should be true, implying that same assignment satisfies $C_m$.

Thus we have $\phi \in$ 3SAT iff $\phi' \in $ ExactOneSAT.

We have actually prove ExactOne3SAT is NP-complete by this because every clause has 3 literals.