World's most popular travel blog for travel bloggers.

Validity of reduction (3-SAT)

, , No Comments
Problem Detail: 

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)$.


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)$


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?

Asked By : D. Giver
Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback