We study the computational complexity of an optimization version of the constraint satisfaction problem: given a set F of constraint functions, an instance consists of a set of variables V related by constraints chosen from F and a natural number k. The problem is to decide whether there exists a subset VV such that Vk and the subinstance induced by V has a solution. For all possible choices of F, we show that this problem is either NP-hard or trivial. This hardness result makes it interesting to study relaxations of the problem which may have better computational properties. Thus, we study the approximability of the problem and we consider certain compilation techniques. In both cases, the results are not encouraging.
展开▼
