Next: MINIMUM NUMBER OF SATISFIABLE Up: Propositional Logic Previous: MAXIMUM WEIGHTED SATISFIABILITY WITH Index

### MAXIMUM 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 [267].

- Comment: Transformation from LONGEST INDUCED PATH. Not approximable within |C|.