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

### MINIMUM 3DNF SATISFIABILITY

- INSTANCE: Set U of variables, collection C of conjunctive clauses of at most three literals, where a literal is a variable or a negated variable in U.

- SOLUTION: A truth assignment for U.

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

- Bad News: Not in APX [312].

- Garey and Johnson: LO8