An Algebraic Approach to Valued Constraint Satisfaction
An Algebraic Approach to Valued Constraint Satisfaction
复制标题
有价值约束满足的代数方法
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Amanda Vidal
中科院分区：
文献类型：
--
作者：
Rostislav Horcík;T. Moraschini;Amanda Vidal
本文以积分有界线性阶monoids的一般框架作为赋值结构，研究了任意模板上赋值CSP （VCSP，简称VCSP）的复杂度。这里考虑的一类问题包含并推广了VCSP文献中最常见的一类问题，因为在约束的表述中允许单轴和格连接操作。对于局部有限单群，我们引入了一个多态的概念，以盖革结果的形式捕捉pp-可定义性。结果表明，与某些多态性的存在性有关的经典CSP的可追溯性的充分条件也适用于有值情况。最后，我们建立了VCSP的二分类猜想，并对经典CSP的二分类进行模化。
We study the complexity of the valued CSP (VCSP, for short) over arbitrary templates, taking the general framework of integral bounded linearly order monoids as valuation structures. The class of problems considered here subsumes and generalizes the most common one in VCSP literature, since both monoidal and lattice conjunction operations are allowed in the formulation of constraints. Restricting to locally finite monoids, we introduce a notion of polymorphism that captures the pp-definability in the style of Geiger’s result. As a consequence, sufficient conditions for tractability of the classical CSP, related to the existence of certain polymorphisms, are shown to serve also for the valued case. Finally, we establish the dichotomy conjecture for the VCSP, modulo the dichotomy for classical CSP.
影响因子：
1.6
作者：
Cohen D
通讯作者：
Cohen D
通用价值 CSP 的复杂性
DOI：
10.1109/focs.2015.80
发表时间：
2015
期刊：
--
影响因子：
--
作者：
Kolmogorov V
通讯作者：
Kolmogorov V