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 
where each clause in F contains all negated or non-negated variables, is there an assignment of the variables so that 
is satisfied?
Example:
the following assignment satisfies :
The reduction:
In the following reduction we are given an instance of SAT, with the clauses:
. Here each clause is of the form 
and each 
is a literal of the form 
Now we build an instance of Monotone SAT from the instance of SAT given above:
For each 
we construct two new clauses 
and 
, such that all elements of 
are non-negated literals and all terms in 
are negated literals with the addition of the new special term 
. Now let us build a new formula 
this is our instance of Monotone SAT, clauses are either all non-negated or negated.
:
Notice how we added the extra literal or 
to each of the clauses or respectfully. Now if there is an assignment that satisfies all of the clauses of then as only 
or 
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 so such an assignment satisfies all 
.
:
Using an argument similar to the one above, For 
to be satisfied there must be at least one literal assignment say 
that satisfies each clause Now is in either or . This implies that at least one of or 
is also satisfied by , so simply assign the new term accordingly to satisfy the clause in not satisfied by
(back to me again)
Difficulty: 3. I like that the reduction involves manipulating the formula, instead of applying logical identities.