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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\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
    Commented Jan 2, 2015 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
    Commented Jan 2, 2015 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
    Commented Jan 2, 2015 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
    Commented Jan 2, 2015 at 16:23
  • $\begingroup$ Alright no problem :) thanks alot for the help mate $\endgroup$
    – D. Giver
    Commented Jan 2, 2015 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.