patternMinor
Reduction from 3 SAT to Monotone Exact 1 in 3 SAT
Viewed 0 times
satexactmonotonereductionfrom
Problem
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.
Solution
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$.
$$ 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$.
Context
StackExchange Computer Science Q#41503, answer score: 6
Revisions (0)
No revisions yet.