Next: MINIMUM 3DNF SATISFIABILITY Up: Propositional Logic Previous: MINIMUM K-SATISFIABILITY Index

### MAXIMUM NOT-ALL-EQUAL 3-SATISFIABILITY

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

- SOLUTION: A truth assignment for U and a subset of the clauses such that each clause in C' has at least one true literal and at least one false literal.

- MEASURE: |C'|.

- Good News: Approximable within 1.138 [272].

- Bad News: APX-complete [371]. Not approximable within 1.090 [453].

- Comment: Transformation from MAXIMUM 2-SATISFIABILITY. Approximable within 1.096 for satisfiable instances [453]. MAXIMUM NOT-ALL-EQUAL SATISFYABILITY, without restrictions on the number of literals in a clause, is approximable within 1.380 [19].

- Garey and Johnson: LO3