MINIMUM NUMBER OF SATISFIABLE FORMULAS

Next: MINIMUM EQUIVALENCE DELETION Up: Propositional Logic Previous: MAXIMUM NUMBER OF SATISFIABLE Index

INSTANCE: Set U of variables, collection C of 3CNF formulas.
SOLUTION: A truth assignment for U.
MEASURE: Number of formulas satisfied by the truth assignment.
Bad News: NPO PB-complete [284].
Comment: Transformation from MINIMUM DISTINGUISHED ONES. Not approximable within $\vert C\vert^{1-\varepsilon }$ for any $\varepsilon >0$ [284].

Viggo Kann
2000-03-20