- INSTANCE:
Set
*U*of variables, boolean expression*F*over*U*, a nonnegative bound , for each variable a weight such that . - SOLUTION:
A truth assignment for
*U*, i.e., a subset such that the variables in*U'*are set to true and the variables in*U-U'*are set to false. - MEASURE:
if the truth assignment satisfies
the boolean expression
*F*and*B*otherwise.

*Good News:*Approximable within 2 [126].*Bad News:*APX-complete [126].*Comment:*Variation in which is PTAS-complete [126].