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.

  • $\begingroup$ Are you happy with a reduction from some other hard problem? $\endgroup$ – Juho Apr 17 '15 at 19:21
  • $\begingroup$ 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).. $\endgroup$ – TheoryQuest1 Apr 17 '15 at 19:37
  • $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ thank you for the hint.. missed the propositional insight.. would try to extend it.. $\endgroup$ – TheoryQuest1 Apr 18 '15 at 7:39
  • $\begingroup$ How do I make sure each clause has exactly one literal per clause is true? $\endgroup$ – rnbguy Feb 26 '18 at 13:43
  • $\begingroup$ You don't. The idea is that the original formula is satisfiable iff there is an assignment to the new formula that satisfies exactly one literal in each clause. $\endgroup$ – Yuval Filmus Feb 26 '18 at 18:08

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.