0
$\begingroup$

I wanted to solve the following problem about 3SAT . The question is 1. to show if the problem is NP-complete and 2. whether the problem has two different satisfying assignments.

"TWICE-3SAT Input: A propositional formula ϕ in conjunctive normal form, such that each clause consists of exactly three literals (as in 3SAT). Question: Does ϕ have at least two different satisfying assignments?"

I understand that we have to use reduction of a known NP-complete problem (such as an independent set) to the problem asked. But I can't go further. I would appreciate your help. I have been working on this for almost a week but I cannot go further.

$\endgroup$

2 Answers 2

1
$\begingroup$

Hint: let $f$ be a 3SAT formula and $w$ a variable not contained in $f$. Then $(w \vee w \vee \overline{w}) \wedge f$ has at least two solutions iff $f$ has at least one.

$\endgroup$
2
  • $\begingroup$ but first shouldn't I reduce a 3sat to twice-3sat to show ϕ is NP-complete? $\endgroup$
    – user217172
    Feb 17, 2015 at 19:44
  • $\begingroup$ That's exactly what this does. $\endgroup$ Feb 17, 2015 at 19:53
0
$\begingroup$

Given a 3-SAT formula $\phi = C_1 \land … \land C_n$, simply add a new clause with three new variables: $C_{n+1} = y_1 \lor y_2 \lor y_3$.

If $x_1,…,x_n$ is a satifying assignment for $\phi$, then the two different assignments $x_1,…,x_n,y_1=\text{true},y_2=\text{false},y_3=\text{false}$ and $x_1,…,x_n,y_1=\text{false},y_2=\text{true},y_3=\text{false}$ both satisfies the new formula $\phi’$. Vice-versa if $\phi$ is not satisfiable, then $\phi’$ is also not satisfiable.

$\endgroup$

You must log in to answer this question.