Next: MINIMUM LENGTH EQUIVALENT FREGE Up: Propositional Logic Previous: MINIMUM EQUIVALENCE DELETION Index

### MAXIMUM K-CONSTRAINT SATISFACTION

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

- SOLUTION: A truth assignment for U.

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

- Good News: Approximable within 2k-1 [428].

- Bad News: APX-complete [71].

- Comment: Transformation from MAXIMUM 2-SATISFIABILITY. Approximable within 1.165 but not within 1.111 for k=2, and approximable within 2 but not within 2 for k=3. There are also results of specific variations of the problem for [453]. Not approximable within 20.09k for large enough k [428]. Not in APX when [434]. When there are exactly k variables in each clause and the number of clauses is the problem admits a randomized PTAS [20].