Next: MINIMUM NUMBER OF SATISFIABLE
Up: Propositional Logic
Previous: MAXIMUM WEIGHTED SATISFIABILITY WITH
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 [282].
- Comment:
Transformation from LONGEST INDUCED PATH.
Not approximable within
.
Viggo Kann
2000-03-20