problems on algorithms for np-completeness, one in three 3SAT, Prove that O3SAT2
ID: 3580186 • Letter: P
Question
problems on algorithms for np-completeness, one in three 3SAT, Prove that O3SAT2 is NP-complete
12.5 ONE-IN-THREE 3SAT Czillsidler ihc followiu" variallis of (hie.nl. Thr.3SA'l' One-in-Three 3SAT (O3SAT1) INSTANCE: A list of clauses C in which each clause contains at most three literals QUESTION: Is there a truth assignment for C in which each clause One-in-Three 3SAT (O3SAT2) INSTANCE: A list of clauses C in which each clause contains exactly three literals QUESTION: Is there a truth assignment for C in which each clause One-in-Three 3SAT (O3SAT3) INSTANCE: A list of clauses C in which each clause contains exactly QUESTION: Is there a truth assignment for C in which each clause contains exactly one true variable?Explanation / Answer
Lets have a function f that takes a CNF formula , in CNF, and produces a new formula f() such that f() is in 3- CNF and the two formulas are either both satisfiable or both unsatisfiable. If we can make and f() equivalent, as sure it would do, but there’s no reason to think that an arbitrary CNF formula will even have a 3-CNF equivalent form. (Every formula can be translated into CNF if we want it to be, but not necessarily into 3-CNF.)
Instead we will make f() have a different meaning from , and also a different set of variables. We will add variables to f() in such a manner that a satisfying setting of both old and new variables of f() will exist if and only if there is a satisfying setting of the old variables alone in . In fact, these old variables will be set in the same way in each formula. Because is in CNF, we know that it is the AND of clauses, which we may name (`11 . . . `1k1 ), (`21 . . . `2k2 ),. . .(`1m . . . `mkm ), where the `’s are each literals. For each and every clauses in , we will make one or more 3-CNF clauses in f(), possibly including new variables, so that the one clause in will be satisfied if all the corresponding clauses in f() are satisfied.
So, now let’s consider a single clause `1. . .`k in . If k 3, we can simply copy the clause over to f(), because it is already suitable for a CNF formula. What if here k = 4 ? We can then add one extra variable and make two clauses: (`1 `2 x1) and (¬x1 `3 `4). It’s not too hard to see that both of these clauses are satisfied if at least one of the `’s is true. If `1 or `2 is true, we can afford to make x1 false, and if `3 or `4 is true, we can make x1 as true. The general construction for k > 4 is similar. We have k 2 clauses and k 3 as new variables:
The clauses are (`1 `2 x1), (¬x1 `3 x2), (¬x2 `4 x3), and so on until we reach (¬xk4 `k2 xk3) and finally (¬xk3 `k1 `k). If we satisfy the original clause with some `i , this satisfies one of the new clauses, and we can satisfy the others by making all the xi’s before to true and all those after it as false. Conversely, if we satisfy all of the new clauses, then we will not be able to do it only with xi’s because there are more clauses than xi’s and each of xi only appears at most once as true and at most once as false, and so can satisfy at most one clause.
Since this reduction is easily computable in polynomial time, it shows that CNF-SAT p 3-SAT, and thus (with the quoted result that O3SAT2 and O3SAT3 is NP-complete) that 3- SAT is NP-complete
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.