- INSTANCE:
Set
*U*of variables, collection*C*of disjunctive clauses of 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.

*Good News:*Approximable within 1.2987 [41].*Bad News:*APX-complete [393].*Comment:*Variation in which each clause has a nonnegative weight and the objective is to maximize the total weight of the satisfied clauses is also approximable within 1.2987 [41]. Generalization in which each clause is a disjunction of conjunctions of literals and each conjunction consists of at most*k*literals, where*k*is a positive constant, is still APX-complete [393]. Admits a PTAS for `planar' instances [304]. The corresponding minimization problem MINIMUM SATISFIABILITY is approximable within 2 [80] and its variation in which each clause has a nonnegative weight and the objective is to minimize the total weight of the satisfied clauses is as hard to approximate as the unweighted version [128].*Garey and Johnson:*LO1