Next:
LO2 MAXIMUM K-SATISFIABILITY
Up:
Propositional Logic
Previous:
Propositional Logic
-
I
NSTANCE
:
Set
U
of variables, collection
C
of disjunctive clauses of literals,
where a literal is a variable or a negated variable in
U
.
-
S
OLUTION
:
A truth assignment for
U
.
-
M
EASURE
:
Number of clauses satisfied by the truth assignment.
-
Good News:
Approximable within 1.3193 [
135
].
-
Bad News:
A
PX
-complete [
284
].
-
Comment:
Variation in which each clause has a nonnegative weight and the
objective is to maximize the total weight of the satisfied clauses is
also approximable within 1.3193 [
135
].
Generalization in which each clause is a disjunction of conjunctions of
literals and each conjunction consists of at most
k
literals, where
k
is a positive constant, is still A
PX
-complete
[
284
].
Admits a PTAS for `planar' instances [
216
].
The corresponding minimization problem M
INIMUM
S
ATISFIABILITY
is approximable within 2
[
52
].
-
Garey and Johnson:
LO1
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997