- INSTANCE:
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 . - SOLUTION:
Truth assignment for
*X*and*Z*that satisfies every clause in*C*. - MEASURE:
The number of
*Z*variables that are set to true in the assignment.

*Bad News:*NPO PB-complete [284].*Comment:*Transformation from MINIMUM INDEPENDENT DOMINATING SET. Not approximable within for any [279]. MINIMUM ONES, the variation in which all variables are distinguished, i.e. , is also NPO PB-complete [284], and is not approximable within for any [279]. MINIMUM ONES for clauses of 2 literals is approximable within 2 [210]. MINIMUM WEIGHTED SATISFIABILITY, the weighted version, in which every variable is assigned a nonnegative weight, is NPO-complete [388]. Variations corresponding to three- and four-valued logics have also been considered [145].