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 条

[41] Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
Larrosa, J
Dechter, R
CONSTRAINTS, 2003, 8 (03) : 303 - 326
[42] Applying constraint satisfaction approach to solve product configuration problems with cardinality-based configuration rules
Yang, Dong
Dong, Ming
JOURNAL OF INTELLIGENT MANUFACTURING, 2013, 24 (01) : 99 - 111
[43] The complexity of homomorphism and constraint satisfaction problems seen from the other side
Grohe, Martin
JOURNAL OF THE ACM, 2007, 54 (01)
[44] Applying constraint satisfaction approach to solve product configuration problems with cardinality-based configuration rules
Dong Yang
Ming Dong
Journal of Intelligent Manufacturing, 2013, 24 : 99 - 111
[45] Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy
Brakensiek, Joshua
Guruswami, Venkatesan
SODA'18: PROCEEDINGS OF THE TWENTY-NINTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2018, : 1782 - 1801
[46] Iterative projection algorithms for solving constraint satisfaction problems: Effect of constraint convexity
Millane, Rick P.
Taylor, Joshua T.
Arnal, Romain D.
Wojtas, David H.
Clare, Richard M.
2019 INTERNATIONAL CONFERENCE ON IMAGE AND VISION COMPUTING NEW ZEALAND (IVCNZ), 2019,
[47] Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
Istrate, Gabriel
ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE, 2024, (410):
[48] The Dichotomy for Conservative Constraint Satisfaction Problems Revisited
Barto, Libor
26TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2011), 2011, : 301 - 310
[49] Perturbed Message Passing for Constraint Satisfaction Problems
Ravanbakhsh, Siamak
Greiner, Russell
JOURNAL OF MACHINE LEARNING RESEARCH, 2015, 16 : 1249 - 1274
[50] On the complexity of trial and error for constraint satisfaction problems
Ivanyos, Gabor
Kulkarni, Raghav
Qiao, Youming
Santha, Miklos
Sundaram, Aarthi
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2018, 92 : 48 - 64

← 1 2 3 4 5 →