Next: MAXIMUM WEIGHTED SATISFIABILITY WITH
Up: Propositional Logic
Previous: MAXIMUM DISTINGUISHED ONES
Disjoint sets X,Z of variables, collection C of disjunctive clauses of
at most 3 literals, where a literal is a variable or a negated variable in
Truth assignment for X and Z that satisfies every clause in C.
The number of Z variables that are set to true in the assignment.
- Bad News:
NPO PB-complete .
Transformation from MINIMUM INDEPENDENT DOMINATING SET.
Not approximable within
MINIMUM ONES, the variation in which all variables are distinguished, i.e.
is also NPO PB-complete , and is not
MINIMUM ONES for clauses of 2 literals is approximable within 2 .
MINIMUM WEIGHTED SATISFIABILITY, the weighted version, in which every variable is assigned
a nonnegative weight, is NPO-complete .
Variations corresponding to three- and four-valued logics have also been