The Complexity of the Distributed Constraint Satisfaction Problem

被引:3
作者
Butti, Silvia [1 ]
Dalmau, Victor [1 ]
机构
[1] Univ Pompeu Fabra, Dept Informat & Commun Technol, Barcelona, Spain
来源
38TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2021) | 2021年 / 187卷
关键词
Constraint Satisfaction Problems; Distributed Algorithms; Polymorphisms;
D O I
10.4230/LIPIcs.STACS.2021.20
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We study the complexity of the Distributed Constraint Satisfaction Problem (DCSP) on a synchronous, anonymous network from a theoretical standpoint. In this setting, variables and constraints are controlled by agents which communicate with each other by sending messages through fixed communication channels. Our results endorse the well-known fact from classical CSPs that the complexity of fixed-template computational problems depends on the template's invariance under certain operations. Specifically, we show that DCSP(Gamma) is polynomial-time tractable if and only if Gamma is invariant under symmetric polymorphisms of all arities. Otherwise, there are no algorithms that solve DCSP(Gamma) in finite time. We also show that the same condition holds for the search variant of DCSP. Collaterally, our results unveil a feature of the processes' neighbourhood in a distributed network, its iterated degree, which plays a major role in the analysis. We explore this notion establishing a tight connection with the basic linear programming relaxation of a CSP.
引用
收藏
页数:18
相关论文
共 50 条
[41]   Promise and Infinite-Domain Constraint Satisfaction [J].
Mottet, Antoine .
32ND EACSL ANNUAL CONFERENCE ON COMPUTER SCIENCE LOGIC, CSL 2024, 2024, 288
[42]   Solution techniques for constraint satisfaction problems: Foundations [J].
Miguel, I ;
Shen, Q .
ARTIFICIAL INTELLIGENCE REVIEW, 2001, 15 (04) :243-267
[43]   Asynchronous Systems for Constraint Satisfaction: Filtering and Stability [J].
Lahlou, Tarek A. ;
Baran, Thomas A. .
2016 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING PROCEEDINGS, 2016, :4816-4820
[44]   CONSTRAINT SATISFACTION NEURAL NETWORKS FOR IMAGE RECOGNITION [J].
TSAO, ECK ;
LIN, WC ;
CHEN, CT .
PATTERN RECOGNITION, 1993, 26 (04) :553-567
[45]   A scaling algorithm for polynomial constraint satisfaction problems [J].
Domes, Ferenc ;
Neumaier, Arnold .
JOURNAL OF GLOBAL OPTIMIZATION, 2008, 42 (03) :327-345
[46]   Constraint Satisfaction, Irredundant Axiomatisability and Continuous Colouring [J].
Jackson, Marcel ;
Trotta, Belinda .
STUDIA LOGICA, 2013, 101 (01) :65-94
[47]   Constraint satisfaction problems solved by semidefinite relaxations [J].
Department of Mathematics and Computer Science, Faculty of Science and Technology of Fez, University Sidi Mohammed Ben Abdellah, Morocco .
WSEAS Trans. Comput., 2008, 7 (951-961)
[48]   QUIET PLANTING IN THE LOCKED CONSTRAINT SATISFACTION PROBLEMS [J].
Zdeborova, Lenka ;
Krzakala, Florent .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2011, 25 (02) :750-770
[49]   Constraint Satisfaction, Irredundant Axiomatisability and Continuous Colouring [J].
Marcel Jackson ;
Belinda Trotta .
Studia Logica, 2013, 101 :65-94
[50]   Interval Constraint Satisfaction: Towards Edge Acceleration [J].
Khun, Jiri ;
Schmidt, Jan .
2022 11TH MEDITERRANEAN CONFERENCE ON EMBEDDED COMPUTING (MECO), 2022,