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.
Comment:
Transformation from MAXIMUM NUMBER OF SATISFIABLE
FORMULAS [389].
Not approximable within
for any
[279].
MAXIMUM ONES, the variation in which all variables are distinguished,
i.e. ,
is also NPO PB-complete [282],
and is not approximable within
for any
[279].
MAXIMUM WEIGHTED SATISFIABILITY, the weighted version, in which every variable is assigned
a nonnegative weight, is NPO-complete
[47].
.
for any
[279].
MAXIMUM ONES, the variation in which all variables are distinguished,
i.e. 
,
is also NPO PB-complete [282],
and is not approximable within
for any