Next:
Miscellaneous
Up:
Propositional Logic
Previous:
LO11 MINIMUM EQUIVALENCE
-
I
NSTANCE
:
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,
.
-
S
OLUTION
:
A truth assignment for
U
.
-
M
EASURE
:
Number of clauses satisfied by the truth assignment.
-
Good News:
Approximable within
[
331
].
-
Bad News:
A
PX
-complete [
49
].
-
Comment:
Transformation from M
AXIMUM
2-S
ATISFIABILITY
. For large enough
k
, it is not
approximable within
[
331
].
Not in A
PX
when
[
337
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997