Next: MAXIMUM NOT-ALL-EQUAL 3-SATISFIABILITY Up: Propositional Logic Previous: MAXIMUM K-SATISFIABILITY Index

### MINIMUM K-SATISFIABILITY

- INSTANCE: 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, .

- SOLUTION: A truth assignment for U.

- MEASURE: Number of clauses satisfied by the truth assignment.

- Good News: Approximable within 2(1-1/2k) [74].

- Bad News: APX-complete for every [311].

- Comment: 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 [311].

- Garey and Johnson: LO2