# Satisfying assignments, twice-3SAT NP complete [duplicate]

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.

• Cross-posted from cstheory: cstheory.stackexchange.com/questions/30523/… - please do not cross-post. Have you tried to actually come up with a reduction, or has all your effort been to decide that you need to come up with a reduction and that you basically didn't know what that entails? Reducing from Independent Set seems strange, it might be helpful to pick a problem that is somewhat similar to the problem at hand. Commented Feb 17, 2015 at 19:38
• Precisely this question is covered in our reference question. This has also been asked once separately with the name double SAT.
– Juho
Commented Feb 17, 2015 at 20:15
• juho can you please post me the link for the reference question? tom thank you for your suggestion. I have tried to come up with reduction. but I would like to see an example of twice-3sat so that I can reduce a 3-sat to twice-3sat. I have searched all over the place about the concept of twice-3sat. thanks once again
– user28838
Commented Feb 17, 2015 at 21:12