- 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 [80].*Bad News:*APX-complete for every [328].*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*[328]. The same variation admits a PTAS for*k=2*if the number of occurrences of each variable is [66].*Garey and Johnson:*LO2