Many researchers in artificial intelligence are beginning to explore the use
of soft constraints to express a set of (possibly conflicting) problem
requirements. A soft constraint is a function defined on a collection of
variables which associates some measure of desirability with each possible
combination of values for those variables. However, the crucial question of the
computational complexity of finding the optimal solution to a collection of
soft constraints has so far received very little attention.