Next:
LO10 MINIMUM NUMBER
Up:
Propositional Logic
Previous:
LO8 MAXIMUM WEIGHTED
-
I
NSTANCE
:
Set
U
of variables, collection
C
of 3CNF formulas.
-
S
OLUTION
:
A truth assignment for
U
.
-
M
EASURE
:
Number of formulas satisfied by the truth assignment.
-
Bad News:
NPO PB-complete [
200
].
-
Comment:
Transformation from L
ONGEST
I
NDUCED
P
ATH
.
Not approximable within
|C|
.
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997