1
$\begingroup$

There is a variable set V = {x1,x2,x3} and clause set C1={x1,x2,-x3} C2={x1,-x1,-x2} C3={-x1,-x2,x3} C4={x2,x3,-x3}. For this structure, no matter each variable is positive or negative, the clause can always be TRUE by at least one literal is TRUE within each clause, just like 3SAT. How can I change the variable gadgets and clause gadgets to make it no matter each variable is positive or negative, the clause can always be TRUE by only one literal is TRUE within each clause, just like 1 in3 3SAT?

$\endgroup$
0
$\begingroup$

Your question is not quite clear, but I believe you are asking how to show that 1in3SAT is NP-complete via a reduction from the known NP-complete problem 3SAT.

If this is your question, then consider the following set up, using your notation: Let an instance of 3SAT be defined by a set of $n$, Boolean variables $V = \{x_1, ..., x_n\}$ and a Boolean equation of $m$ clauses $\Phi = C_1 \land C_2 \land...\land C_m$ where each $C_j = (x_{j_1}\lor x_{j_2} \lor x_{j_3})$.

To reduce this to 1in3SAT begin the reduction in the following manner. For each $C_j$ create 3 new clauses $C'_{j,1} = (\lnot x_{j_1}\lor \alpha_j \lor \beta_j) $, $C'_{j,1} = (x_{j_2}\lor \beta_j \lor \gamma_j) $, and $C'_{j,3} = (\lnot x_{j_3}\lor \gamma_j \lor \delta_j) $ where $\alpha_j, \beta_j, \gamma_j, \delta_j$ are new Boolean random variables. Let $\Phi'$ be the Boolean equation in your 1in3SAT instance which now the AND over your these new clauses. That is, you now have $3m$ clauses and $n + 4m$ variables.

Next, think about what would happen if we had a true assignment for the 3SAT instance, then what would happen if we had a valid assignment for the newly constructed 1in3SAT instance (this second direction will be much easier.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ No actually this is not what Im asking for, what Im asking is: How to change the provided clause gadgets and variable gadgets to fit 1in3 3SAT for this case. variable set V = {x1,x2,x3} and clause setC: C1={x1,x2,-x3} C2={x1,-x1,-x2} C3={-x1,-x2,x3} C4={x2,x3,-x3}. How to change them to let them no matter the three variables is positive or negative, each clause will have and only have one literal is true. Plus, the number of clause and variables and the literals all can be changed. If still not clear please let me know. Thank you. $\endgroup$ – Richie Li Aug 30 '19 at 4:46
  • $\begingroup$ @RichieLi Your question is even more restricted then, and sounds a lot like a homework problem. But good new, you can easily use the idea I provided to solve your question! $\endgroup$ – Barcode Aug 30 '19 at 4:57
  • $\begingroup$ actually at the first time I just mimic the above method, but teacher said there could be some other way that not force any variable to be true or false, every variable should be flexible to choose positive and negative $\endgroup$ – Richie Li Aug 30 '19 at 5:05
  • $\begingroup$ Given a 3SAT clause (a,b,c) consider the clause (a, ~ab, ~a~bc). Only one of a, ~ab, or ~a~bc can be true if the clause (a,b,c) is satisfied. $\endgroup$ – Russell Easterly Mar 16 at 20:58
0
$\begingroup$

A 1-in-3 SAT clause (A,B,C) can be expressed with the following 5 clauses in 3SAT.

$(A ∨ B ∨ C) $

$(A ∨ \overline{B} ∨ \overline{C}) $

$(\overline{A} ∨ B ∨ \overline{C}) $

$(\overline{A} ∨ \overline{B} ∨ C) $

$(\overline{A} ∨ \overline{B} ∨ \overline{C}) $

Why? Consider the truth table over A,B,C.

| A | B | C |   | A | B | C |
| 0 | 0 | 0 |   | --------- |
| 0 | 0 | 1 |   | 0 | 0 | 1 | 
| 0 | 1 | 0 |   | 0 | 1 | 0 | 
| 0 | 1 | 1 |   | --------- | 
| 1 | 0 | 0 |   | 1 | 0 | 0 |
| 1 | 0 | 1 |   | --------- | 
| 1 | 1 | 0 |   | --------- |
| 1 | 1 | 1 |   | --------- |

There are 8 lines. Each clause eliminates 1 line. We only want to allow (0,0,1), (0,1,0), (1,0,0) and eliminate the others.

| cite | improve this answer | |
$\endgroup$

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.