Next: MAXIMUM WEIGHTED SATISFIABILITY WITH Up: Propositional Logic Previous: MAXIMUM DISTINGUISHED ONES Index

### MINIMUM DISTINGUISHED ONES

- 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 [269].

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