Nonuniform Boolean Constraint Satisfaction Problems with Cardinality Constraint

被引：7
作者：
Creignou, Nadia [1 ]
Schnoor, Henning [2 ]
Schnoor, Ilka [3 ]
机构：
[1] Aix Marseille Univ, Marseille, France
[2] Univ Kiel, D-24118 Kiel, Germany
[3] Med Univ Lubeck, D-23562 Lubeck, Germany
来源：
ACM TRANSACTIONS ON COMPUTATIONAL LOGIC | 2010年 / 11卷 / 04期
关键词：
Theory; Computational complexity; constraint satisfaction; COMPLEXITY; SATISFIABILITY; BASES;
D O I：
10.1145/1805950.1805954
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We study the computational complexity of Boolean constraint satisfaction problems with cardinality constraint. A Galois connection between clones and coclones has received a lot of attention in the context of complexity considerations for constraint satisfaction problems. This connection does not seem to help when considering constraint satisfaction problems that support in addition a cardinality constraint. We prove that a similar Galois connection, involving a weaker closure operator and partial polymorphisms, can be applied to such problems. Thus, we establish dichotomies for the decision as well as for the counting problems in Schaefer's framework.
引用
收藏
页码：1 / 32
页数：32
相关论文
共 29 条
[1]  
Allender E, 2005, LECT NOTES COMPUT SC, V3618, P71
[2]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[3]  
Bauland M, 2005, LECT NOTES COMPUT SC, V3618, P119
[4]  
BAZGAN C, 2005, P INT S ALG COMP ISA, P624
[5]   Adding cardinality constraints to integer programs with applications to maximum satisfiability [J].
Blaeser, Markus ;
Heynen, Thomas ;
Manthey, Bodo .
INFORMATION PROCESSING LETTERS, 2008, 105 (05) :194-198
[6]  
Bodnarchuk V. G., 1969, Cybernetics, V5, P243, DOI 10.1007/BF01070906
[7]  
Bodnarchuk V. G., 1969, Cybernetics, V5, P531, DOI 10.1007/BF01267873
[8]   Bases for Boolean co-clones [J].
Böhler, E ;
Reith, S ;
Schnoor, H ;
Vollmer, H .
INFORMATION PROCESSING LETTERS, 2005, 96 (02) :59-66
[9]  
Böhler E, 2004, LECT NOTES COMPUT SC, V2996, P164
[10]  
Böhler E, 2002, LECT NOTES COMPUT SC, V2471, P412
123