I am interested in a SAT variation where the CNF formula is monotone (no variables are negated). Such a formula is obviously satisfiable.
But say the number of true variables is a measure of how good our solution is. So we have the following problem:
MINIMUM TRUE MONOTONE 3SAT
INSTANCE: Set U of variables, collection C of disjunctive clauses of 3 literals, where a literal is a variable (not negated).
SOLUTION: A truth assignment for U that satisfies C.
MEASURE: The number of variable that are true.
Could someone give me some helpful remarks on this problem?