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

共 50 条

[1] Constraint Satisfaction Problems and Global Cardinality Constraints
Bulatov, Andrei A.
Marx, Daniel
COMMUNICATIONS OF THE ACM, 2010, 53 (09) : 99 - 106
[2] The complexity of Boolean constraint satisfaction local search problems
Chapdelaine, P
Creignou, N
ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2005, 43 (1-4) : 51 - 63
[3] The complexity of Boolean constraint satisfaction local search problems
Philippe Chapdelaine
Nadia Creignou
Annals of Mathematics and Artificial Intelligence, 2005, 43 : 51 - 63
[4] Frozen variables in random boolean constraint satisfaction problems
Molloy, Michael
Restrepo, Ricardo
PROCEEDINGS OF THE TWENTY-FOURTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA 2013), 2013, : 1306 - 1318
[5] Tractability in constraint satisfaction problems: a survey
Carbonnel, Clement
Cooper, Martin C.
CONSTRAINTS, 2016, 21 (02) : 115 - 144
[6] Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case
Barto, Libor
Battistelli, Diego
Berg, Kevin M.
38TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2021), 2021, 187
[7] Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems
Galanis, Andreas
Goldberg, Leslie Ann
Yang, Kuan
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2021, 115 : 187 - 213
[8] Boolean constraint satisfaction: complexity results for optimization problems with arbitrary weights
Jonsson, P
THEORETICAL COMPUTER SCIENCE, 2000, 244 (1-2) : 189 - 203
[9] Complexity of Conservative Constraint Satisfaction Problems
Bulatov, Andrei A.
ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2011, 12 (04)
[10] The Complexity of Temporal Constraint Satisfaction Problems
Bodirsky, Manuel
Kara, Jan
JOURNAL OF THE ACM, 2010, 57 (02)

← 1 2 3 4 5 →