[Math] Satisfying assignments, twice-3SAT NP complete

np-completesatisfiability

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.

Best Answer

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.

Related Question