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 [267].
- Comment:
Transformation from LONGEST INDUCED PATH.
Not approximable within |C|.
Viggo Kann
1999-04-22