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

### MINIMUM NUMBER OF SATISFIABLE FORMULAS

- 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 [269].

- Comment: Transformation from MINIMUM DISTINGUISHED ONES. Not approximable within for any [269].