Next: MINIMUM DISTINGUISHED ONES
Up: Propositional Logic
Previous: MINIMUM 3DNF SATISFIABILITY
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
Truth assignment for X and Z that satisfies every clause in C.
The number of Z variables that are set to true in the assignment.
- Bad News:
NPO PB-complete .
Transformation from MAXIMUM NUMBER OF SATISFIABLE
Not approximable within
MAXIMUM ONES, the variation in which all variables are distinguished,
is also NPO PB-complete ,
and is not approximable within
MAXIMUM WEIGHTED SATISFIABILITY, the weighted version, in which every variable is assigned
a nonnegative weight, is NPO-complete