5
$\begingroup$

$\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.

$\endgroup$
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? Hint: for every clause in the formula, add some variables and create several clauses. $\endgroup$ – Shaull Feb 14 '16 at 8:39
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sorry but I am unable to follow why this approach would work for the example I mentioned. Could you please explain. $\endgroup$ – sashas Feb 14 '16 at 9:49
  • $\begingroup$ $\phi \in$ 3SAT iff $\phi' \in $ ExactOneSAT is the crux of matter. from an assignment of $\phi$ we can easily get one-assignment for $\phi'$ and vice-versa. $\endgroup$ – Shreesh Feb 14 '16 at 9:51
  • 1
    $\begingroup$ @Shreesh How do we ensure that each of the two-literal clauses have only one true literal in them? For instance, if all of the literals in the original clause are true and there is only one true literal in each of the resulting 2-literal clauses then we must have all the new variables set to true. But then the new 3-literal clause has three true literals in it not exactly one. $\endgroup$ – Ari Feb 29 '16 at 20:47
  • $\begingroup$ @Ari, thank you for pointing out the mistake. I have corrected the answer and have expanded the explanation. $\endgroup$ – Shreesh Mar 1 '16 at 6:40

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.