# Validity of reduction (3-SAT)

I'm trying to show that a special variant of the common 3-SAT is NP-complete by reducing 3-SAT to this special variant.

This special variant works like the normal 3CNF-SAT, except every other clause is conjunctive instead of disjunctive. For example an instance of this variant could be $(x \vee y \vee z) \wedge (x\wedge w\wedge k) \wedge (y \vee \neg{}z \vee f)$.

EDIT:

Would the following work? If I want to reduce $from$ 3-SAT, I would propose an instance of the 3-SAT variant, and via an algorithm running in polynomial time, transform every other clause (the conjunctive ones) into 3 new disjunctive clauses like the following example.

Instance of 3-Sat Variance $(x \vee y \vee z) \wedge (x\wedge w\wedge k) \wedge (y \vee \neg{}z \vee f)$

Transformation/Reduction $(x \vee y \vee z) \wedge (x\vee x\vee x) \wedge (w \vee w \vee w) \wedge (k \vee k \vee k) \wedge (y \vee \neg{}z \vee f)$

EDIT 2:

Or do you mean I should look at it the other way around?

If I want to prove that this 3-SAT variant is NP-complete, could I for example simply add a new, trival term $z$ not used in the original list of terms (give it TRUE as truth value), and add a clause $(z \wedge z \wedge z)$ inbetween all the original clauses of the original 3-SAT instance?

• The suggestion in the revision doesn't work. For example (in 2CNF but that doesn't matter, $(x\vee \neg x) \wedge (y\vee \neg y)$ is satisfiable but transforms to $(x\vee\neg x) \wedge (y\vee y) \wedge (\neg y \vee \neg y)$, which isn't satisfiable. And you've not added any conjunctive clauses. I've added a bit more hint. – David Richerby Jan 2 '15 at 15:32
• @D.Giver Oops. My second hint wasn't very helpful. :-) I think I misunderstood what you'd written. But, in any case, your answer of inserting "clauses" $z\wedge z\wedge z$ for some new variable $z$ is correct (and exactly what I would have done). – David Richerby Jan 2 '15 at 16:23