1-in-3 SAT is the set of 3CNF formulas with no negated variables such that there is a satisfying assignment that makes exactly one variable in each clause true. Show 1-in-3 SAT is NP-complete

Plan on doing a reduction from 3SAT.

My confusion arises from the "no negated variables". You need some way of representing negated variables. How do you do that? I can do the reduction from 3SAT to 1-in-3 SAT without the restraint that there are no negated variables. I'm just not sure how to do it with this constraint.

  • $\begingroup$ The 1-in-3 part represents the negated variables; 1 is true, the other two are negated. $\endgroup$ – Realz Slaw Nov 12 '13 at 18:03

My confusion arises from the "no negated variables". This is the point of the question. You need to figure out a way to simulate negated variables.

Hint: One way is using a "gadget" that forces $b = \lnot a$ for some variables $a,b$. You can start by coming up with a way of forcing certain auxiliary variables to be True or False.

  • $\begingroup$ YuvalFilmus Does this work: for some clause that has a,b,c. we take the variable (e.g.) and create a new clause: (a v d_x v d_x). d_x is a dummy variable that is forced to be fals $\endgroup$ – lars Nov 12 '13 at 18:33
  • 1
    $\begingroup$ That forces $d_x$ to be false and $a$ to be true, which is not quite what you wanted, but a good start. This gives a way of ensuring some variables are false and some are true. Now how can you use it to express something like $a \leftrightarrow \lnot b$? $\endgroup$ – Yuval Filmus Nov 12 '13 at 18:34
  • $\begingroup$ if the clause is (x v -y v z), then we change it to: (x v y v z) and (d_y v y v y). $\endgroup$ – lars Nov 12 '13 at 21:05
  • $\begingroup$ That doesn't quite work - it forces $y$ to be negative. You want $y$ to be able to have both values. But if you had two clauses $(y \lor \cdots)$ and $(\lnot y \lor \cdots)$, you want to replace them with $(y^+ \lor \cdots)$ and $(y^- \lor \cdots)$, where $y^+$ and $y^-$ have opposite values. $\endgroup$ – Yuval Filmus Nov 12 '13 at 21:31
  • $\begingroup$ If the clause is (x v -y v z) don't you want to force why to be negative? $\endgroup$ – lars Nov 13 '13 at 1: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.