# Reduction from 3 SAT to Monotone Exact 1 in 3 SAT

Can someone please help with a clear reduction from a 3SAT to a Monotone Exact 1 in 3 SAT. I tried searching by didn't find much.

• Are you happy with a reduction from some other hard problem? – Juho Apr 17 '15 at 19:21
• thx for comment.. i prefer to use 3SAT as i am studying that.. but it would be good even if i get some other reduction (as i can try to reduce the other from to 3SAT myself).. – TheoryQuest1 Apr 17 '15 at 19:37
• What have you tried? Where did you get stuck? Have you tried looking for a reduction from some other problem of your choice to Monotone Exact 1 in 3 SAT? Have you been able to find any other problem where you are able to make that reduction work? (If so, then all you need is a reduction from 3SAT to that other problem.) We expect you to make a significant effort before asking, and that's one idea to get you started and one way you can try to make partial progress on your question on your own. – D.W. Apr 17 '15 at 21:43

Here are some ideas to get you started. You can find on the internet simple gadget reductions from 3SAT to 1-in-3SAT. In monotone 1-in-3SAT you are not allowed to use negations, but if you allow clauses of width 2, you can add clauses $$x_i^+ \lor x_i^-$$ for each variable $i$. This clause forces $x_i^- = \lnot x_i^+$, and so allows you to simulate negations. If you really insist that your clauses have width 3, you need to be slightly more devious. Try to figure out a way yourself, and only if you're unsuccessful, take a look at my solution below:
For example, you can add three new variables $a,b,c$, replace $x_i^+ \lor x_i^-$ with the pair of clauses $x_i^+ \lor x_i^- \lor a$, $x_i^+ \lor x_i^- \lor b$, and add the clause $a \lor b \lor c$.