Next: MINIMUM LENGTH EQUIVALENT FREGE
Up: Propositional Logic
Previous: MINIMUM EQUIVALENCE DELETION
  Index
- 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].
Viggo Kann
1999-04-22