Next: MAXIMUM NUMBER OF SATISFIABLE
Up: Propositional Logic
Previous: MINIMUM DISTINGUISHED ONES
Set U of variables, boolean expression F over U, a nonnegative bound
for each variable
A truth assignment for U, i.e., a subset
such that the
variables in U' are set to true and the variables in U-U' are set to false.
if the truth assignment satisfies
the boolean expression F and B otherwise.
- Good News:
Approximable within 2 .
- Bad News:
Variation in which
is PTAS-complete .