# Show 1-in-3 SAT

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.

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

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.
• 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$? – Yuval Filmus Nov 12 '13 at 18:34
• 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. – Yuval Filmus Nov 12 '13 at 21:31