期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1999
卷号：1999
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
