论文标题
分布式约束满意度问题的复杂性
The Complexity of the Distributed Constraint Satisfaction Problem
论文作者
论文摘要
我们从理论的角度研究了在同步的匿名网络上分布式约束满意度问题（DCSP）的复杂性。在这种情况下，变量和约束由通过固定通信渠道发送消息相互通信的代理控制。我们的结果认可经典CSP的众所周知的事实，即固定模板计算问题的复杂性取决于某些操作下模板的不变性。具体而言，我们表明，当且仅当$γ$在所有ARITIS的对称多态性下都是不变的，DCSP（$γ$）是多项式时间的处理。否则，将在有限的时间内解决DCSP（$γ$）的算法。我们还表明，DCSP的搜索变体相同条件。在本方面，我们的结果在分布式网络中揭示了该过程的社区的特征，其迭代学位在分析中起着重要作用。我们探索了这个概念，与CSP的基本线性编程放松建立了紧密的联系。
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($Γ$) is polynomial-time tractable if and only if $Γ$ is invariant under symmetric polymorphisms of all arities. Otherwise, there are no algorithms that solve DCSP($Γ$) 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.
