Next: MAXIMUM K-CONSTRAINT SATISFACTION Up: Propositional Logic Previous: MINIMUM NUMBER OF SATISFIABLE Index

### MINIMUM EQUIVALENCE DELETION

- INSTANCE: Set U of variables, collection C of equivalences, i.e., pairs of literals over U.

- SOLUTION: A truth assignment for U.

- MEASURE: Number of equivalences that are not satisfied by the truth assignment.

- Good News: Approximable within [177].

- Bad News: APX-hard [177].

- Comment: The complementary maximization problem is approximable within 1.138 [Kann, --].