2
$\begingroup$

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.

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

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\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
    Commented Nov 12, 2013 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
    Commented Nov 12, 2013 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
    Commented Nov 12, 2013 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
    Commented Nov 12, 2013 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
    Commented Nov 13, 2013 at 1:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.