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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tom van der Zanden
    Feb 17, 2015 at 19:38
  • 1
    $\begingroup$ Precisely this question is covered in our reference question. This has also been asked once separately with the name double SAT. $\endgroup$
    – Juho
    Feb 17, 2015 at 20:15
  • $\begingroup$ 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 $\endgroup$
    – user28838
    Feb 17, 2015 at 21:12

1 Answer 1

Reset to default
0
$\begingroup$

Hints:

  1. Showing that the problem is NP is easy.
  2. To show that it is NP-hard, show first that TWICE-SAT is NP-hard (see next step).
  3. In order to show that TWICE-SAT is NP-hard, reduce from SAT. The idea is to add a "dummy" satisfying assignment, which is always going to be satisfying; any satisfying assignment of the original SAT instance will translate to a (different) satisfying assignment of the new instance.
  4. Either reduce TWICE-SAT to TWICE-3SAT, or use insights from your proof in step 3 to prove that TWICE-3SAT is NP-hard.
Improve this answer
$\endgroup$