Next:
LO4 MAXIMUM NOT-ALL-EQUAL
Up:
Propositional Logic
Previous:
LO2 MAXIMUM K-SATISFIABILITY
-
I
NSTANCE
:
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,
.
-
S
OLUTION
:
A truth assignment for
U
.
-
M
EASURE
:
Number of clauses satisfied by the truth assignment.
-
Good News:
Approximable within
[
52
].
-
Bad News:
A
PX
-complete for every
[
237
].
-
Comment:
Transformation from M
AXIMUM
2-S
ATISFIABILITY
.
Variation in which each clause is a Horn clause, i.e., contains at most
one nonnegated variable, is A
PX
-complete, even for
k=2
[
237
].
-
Garey and Johnson:
LO2
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997