The Complexity of Global Cardinality Constraints
The Complexity of Global Cardinality Constraints
复制标题
全局基数约束的复杂性
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
D. Marx
中科院分区：
文献类型：
--
作者：
A. Bulatov;D. Marx
在约束满足问题（CSP）中，目标是找到一组给定变量在指定约束下的分配。全局基数约束是一个额外的要求，它规定了必须为多少个变量分配某个值。我们研究的复杂性问题CCSP（伽玛），约束满足问题的全局基数约束，只允许从一组伽玛的关系。本文的主要结果的特点集伽玛引起的问题在多项式时间内可解，并指出，其余的这些问题是NP-完全的。
In a constraint satisfaction problem (CSP) the goal is to find an assignment of a given set of variables subject to specified constraints. A global cardinality constraint is an additional requirement that prescribes how many variables must be assigned a certain value. We study the complexity of the problem CCSP(Gamma), the constraint satisfaction problem with global cardinality constraints that allows only relations from the set Gamma. The main result of this paper characterizes sets Gamma that give rise to problems solvable in polynomial time, and states that the remaining such problems are NP-complete.