Monotone Satisfiability

This semester I’m doing an independent study with a student, Daniel Thornton, looking at NP-Complete problems.  He came up with a reduction for Monotone Satisfiability, and since I hadn’t gotten to that problem yet, I told him if he wrote it up, I’d post it.

So, here it is.  Take it away, Daniel!

The Problem: Monotone SAT. This is mentioned in problem LO2 in the book.

The description:
Given an set of clauses F' = \wedge_{i=1}^{n} C_{i} where each clause in F contains all negated or non-negated variables, is there an assignment of the variables so that F' is satisfied?

F' = (x_{1} \vee x_{3} \vee x_{4}) \wedge (\neg x_{2} \vee \neg x_{3} \vee \neg x_{4}) \wedge (x_{3} \vee x_{2} \vee x_{4})
the following assignment satisfies F':
x_{1} \mapsto False
x_{2} \mapsto False
x_{3} \mapsto False
x_{4} \mapsto True

The reduction:
In the following reduction we are given an instance of SAT, with the clauses:
F = \wedge_{i=1}^{n} C_{i}. Here each clause is of the form C_{i} = x_{i1} \vee x_{i2} \vee ... \vee x_{ik_i}and each x_{ij} is a literal of the form \neg z_{ij} \ or \ z_{ij}
Now we build an instance of Monotone SAT from the instance of SAT given above:
For each C_{i} we construct two new clauses \\ C'_{2i} = z_{i l_1} \vee ... \vee z_{il_k } \vee z'_{i} and  \ C'_{2i-1}= \neg z_{il_k+1} \vee ... \vee \neg z_{il_m} \vee \neg z'_{i}, such that all elements of C'_{2i} are non-negated literals and all terms in C'_{2i-1} are negated literals with the addition of the new special term z'_{i}. Now let us build a new formula F' = \wedge_{i'=1}^{2n} C'_{i'} this is our instance of Monotone SAT, clauses are either all non-negated or negated.

True_{Monotone SAT} \Rightarrow True_{SAT}:
Notice how we added the extra literal z'_{i} or \neg z'_{i} to each of the clauses C'_{2i} or C'_{2i-1} respectfully. Now if there is an assignment that satisfies all of the clauses of F' then as only C_{2i} or C_{2i-1} may be satisfied by the appended extra literal, one of the clauses must be satisfied by it’s other literals. These literals are also in C_{i} so such an assignment satisfies all C_{i} \in F.

True_{SAT} \Rightarrow True_{Monotone SAT}:
Using an argument similar to the one above, For F to be satisfied there must be at least one literal assignment say z_{iy} that satisfies each clause C_{i} Now z_{iy} is in either C'_{2i} or C'_{2i-1}. This implies that at least one of C'_{2i} or C'_{2i -1} is also satisfied by z_{iy}, so simply assign the new term z'_{i} accordingly to satisfy the clause in F' not satisfied by z_{iy}

(back to me again)

Difficulty: 3.  I like that the reduction involves manipulating the formula, instead of applying logical identities.

Leave a Reply

Your email address will not be published. Required fields are marked *