LO7 M INIMUM D ISTINGUISHED O NES

     
• I NSTANCE : 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 .
• S OLUTION : Truth assignment for X and Z that satisfies every clause in C .
• M EASURE : The number of Z variables that are set to true in the assignment.

• Bad News: NPO PB-complete [ 202 ].
• Comment: Transformation from M INIMUM I NDEPENDENT D OMINATING S ET . Not approximable within for any [ 197 ]. M INIMUM O NES , the variation in which all variables are distinguished, i.e. , is also NPO PB-complete [ 202 ], and is not approximable within for any [ 197 ].   M INIMUM O NES for clauses of 2 literals is approximable within 2 [ 144 ]. M INIMUM W EIGHTED S ATISFIABILITY , the weighted version, in which every variable is assigned a nonnegative weight, is NPO-complete [ 280 ].   Variations corresponding to three- and four-valued logics have been also considered [ 97 ].