0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

Hint 1. If the conjunctive "clauses" are trivially satisfiable, then any unsatisfiability must be due to the ordinary disjunctive clauses.

Hint 2. You don't have to change any of the clauses of the original CNF.

$\endgroup$
  • $\begingroup$ I think I get what you're saying. I revised my question under the EDIT: tag in the original post. Am I on the right track? $\endgroup$ – D. Giver Jan 2 '15 at 14:47
  • $\begingroup$ 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. $\endgroup$ – David Richerby Jan 2 '15 at 15:32
  • $\begingroup$ Hmm okay, well in my revision im not changing any clauses in the original CNF, im simply adding new ones. I'm changing the conjuctive clause in the special 3-SAT variant. But if I'm still wrong I'll keep thinking and get back to you, thanks for the help so far $\endgroup$ – D. Giver Jan 2 '15 at 15:44
  • $\begingroup$ @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). $\endgroup$ – David Richerby Jan 2 '15 at 16:23
  • $\begingroup$ Alright no problem :) thanks alot for the help mate $\endgroup$ – D. Giver Jan 2 '15 at 17:26

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.