$\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.
How to show ExactOneSAT is NP-Complete?
complexity theory;np complete;satisfiability;3 sat
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 $ 3SATAssume 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.