Next:
LO11 MINIMUM EQUIVALENCE
Up:
Propositional Logic
Previous:
LO9 MAXIMUM NUMBER
-
I
NSTANCE
:
Set
U
of variables, collection
C
of 3CNF formulas.
-
S
OLUTION
:
A truth assignment for
U
.
-
M
EASURE
:
Number of clauses satisfied by the truth assignment.
-
Bad News:
NPO PB-complete [
202
].
-
Comment:
Transformation from M
INIMUM
D
ISTINGUISHED
O
NES
.
Not approximable within
for any
[
202
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997