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?

Example:
$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.

Discussions of NP-Complete Problems

A Resource for Computer Science Educators

Leave a Reply Cancel reply