Next:
LO5 MINIMUM 3DNF
Up:
Propositional Logic
Previous:
LO3 MINIMUM K-SATISFIABILITY
-
I
NSTANCE
:
Set
U
of variables, collection
C
of disjunctive clauses of at most
3 literals, where a literal is a variable or a negated variable in
U
.
-
S
OLUTION
:
A truth assignment for
U
and a subset
of the clauses such
that each clause in
C'
has at least one true literal and at least one
false literal.
-
M
EASURE
:
|C'|
.
-
Good News:
Approximable within 1.138 [
205
].
-
Bad News:
A
PX
-complete [
284
].
-
Comment:
Transformation from M
AXIMUM
2-S
ATISFIABILITY
.
Not approximable within 1.013 [
205
].
-
Garey and Johnson:
LO3
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997