Next: MINIMUM DISTINGUISHED ONES Up: Propositional Logic Previous: MINIMUM 3DNF SATISFIABILITY Index

### MAXIMUM 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 [267].

- Comment: Transformation from MAXIMUM NUMBER OF SATISFIABLE FORMULAS [368]. Not approximable within for any [264]. MAXIMUM ONES, the variation in which all variables are distinguished, i.e. , is also NPO PB-complete [267], and is not approximable within for any [264]. MAXIMUM WEIGHTED SATISFIABILITY, the weighted version, in which every variable is assigned a nonnegative weight, is NPO-complete [44].