, for each variable
a weight
such that
.
such that the
variables in
U'
are set to true and the variables in
U-U'
are set to false.
if the truth assignment satisfies
the boolean expression
F
and
B
otherwise.
is PTAS-complete [
86
].
Viggo Kann