Next: MAXIMUM NOT-ALL-EQUAL 3-SATISFIABILITY
Up: Propositional Logic
Previous: MAXIMUM K-SATISFIABILITY
Set U of variables, collection C of disjunctive clauses of at most
k literals, where a literal is a variable or a negated variable in U.
k is a constant, .
A truth assignment for U.
Number of clauses satisfied by the truth assignment.
- Good News:
- Bad News:
APX-complete for every
Transformation from MAXIMUM 2-SATISFIABILITY.
Variation in which each clause is a Horn clause, i.e., contains at most
one nonnegated variable, is APX-complete, even for k=2 .
The same variation admits a PTAS for k=2 if the number of occurrences of
each variable is
- Garey and Johnson: LO2